I know, Naxx is coming and it can change many things around. Unfortunately it's hard to imagine that one class card is going to make Mages work again - there's just to many issues to cope with.
So my idea is to make Frost Nova into a secret activated whenever an enemy minion attacks. It's already on 3 mana, at the same time it's impact on the board doesn't feel worth the cost - it's awkward to put something relevant behind it, especially in the early-game. Making it a secret would give it some relevance in the early game because of Kirin-Tor and maybe even Arcanist or Secret Keeper. I don't think it would be much of a change to the card itself, because as long as you've got something to trigger it, it still won't affect chargers. The only change from the opposing side of view is just the fact that it would be another secret to work around, though most of the Mage secrets trigger-tests start with going for the face, so this one would be pretty self-solving. This change wouldn't make the card all that much more powerful but it would increase the synergy potential of the class.