The fault may lie with Frostbolt itself. Looking at the damage breakdown at, say, a greater invasion boss, the % of damage that frostbolt contributes is miniscule. Frost is about procs and icicles.
If you want to punch a nuke into their face, I'm surprised at how effective arcane can be. If you can manage the charges well in the open world, it will serve you well and you will hit hard.
What I did when I leveled, since I did do it as frost, was doing as large pulls as possible. Orb, Blizzard and spam lances. That or shatter combos.