Sounds about right. The last pulls in DM are rough <18. Once you hit 20 and get healing stream totems, it's all over but the crying.

You'll get different opinions on this but my most basic recommendation is two-fold:

1) Farm yourself good weapons and gear from instances in between quests, especially if it is stuff that'll last you 10+ levels.
2) Go enhancement spec while leveling at least up through the 40s IMO. I don't know where the good breakover is for switching to elemental but leveling as a gimp caster through those levels is painful, especially considering the itemization issues with shammies in general. Aside from the occasional 70, instance runs have been super-easy as enhancement and have zero downtime. At 30, windfury sped things up a LOT. At 40, dual-wield+windfury is like driving an out-of-control hummer with a huge weed-eater attached to the front of it.

Again, for the purists out there, these are just my opinions relative to playing mages/locks/hunters. I was elemental up through about 15 and the leveling was just sooooo sloooowwww with mana sucking that bad. If you have alts there that have the fiery enchant, you can make the lower levels simply FLY by.

Regarding instance leveling, I usually gauge the effectiveness of my guys by how much downtime they incur. For a mix of greens/blues at most any level, they should roughly perform like so:
Mobs -3 to -5 and bosses -3 or lower = zero downtime, period. If you have downtime of more than a few seconds every 5+ pulls, you're doing something wrong or your gear needs repairs. Bosses should be risk-free kills.
Mobs -3 to +0 and bosses +0 = minor downtime. Shouldn't have to stop to drink/eat until every 3-5 pulls and it should only take you 10-15 secs to recover. Bosses may require a heal or two but should be fairly easy (with obvious caveats where fear/MC/sheep/etc. cause advanced tictacz requirements).
Mobs +0 to +3 and bosses +2 or higher = obviously lots of downtime. Bosses may gank one of you but you should be able to Git R Dun.

If you're not performing at about the above levels, farm more gear, get twink-type enchants or stop speccing straight resto. :P

My 2 cents/pfennigs/pence/etc.