Generally speaking, melee is just easier to level. In the case of shammies, this is compounded by the fact that elemental lacks good damage until higher levels with lava burst, where as as soon as WINfury weapon is unlocked enhance does great damage just by auto attacking.

you answered your question yourself "As far as i can tell the only downside is my mana runs out faster compared to enhancement" not only did you have to wait to get thunderstorm but you also had to use elixirs and with alchemy you probably used a few mana pots (am i right?) leveling in the DF system is fine as you'll be having a few drinks with the healer anyway but when leveling alot of people play the game by questing (traditional way) and dont want/ cant spend G on elixirs mana pots just to decrease there down time whereas by leveling enhancement your down time due to OOM situations is less and you can still (if you have to) do some DPS with no mana
i might be wrong but thats my opinion anyway

There's also the issue that elemental is somewhat broken in raiding, since the spellpower bonus from Totem of Wrath is a non-scaling version of Demonic Pact (and in current raid gear that means inferior), and Wrath replaces your damage dealing totem. If you've got a Demo lock for your raid, your ranged DPS Shaman needs to get into melee range to use their best DPS totem, and if they're stuck using their buff totem they do substandard damage. Admittedly, this doesn't really matter while levelling, but WoW players being who we are, it trickles down.

To be honest, I've seen quite a few levelling elemental shamans, although they're usually using hand-me-down tattered dreadmist pieces.

Personally, I found levelling as elemental fine, although admittedly I never tried it until I hit Northrend so I had the additional regen of thunderstorm right of the bat. You're durable as all get out if you keep a decent shield strapped on your arm, water shield does a decent job of keeping the mana flowing, and lightning bolt has a very nice mana to damage ratio

I went enh till I got to the lvl where I could get totem of wrath by respeccing ele. I found ele to be much more fun, and if talented/stacked correctly the mana regen never becomes an issue. It's been much more fun killing things before they can even get close to me (even if they do, t-storm + FRAWST SHAWK make sure they stay away) than getting my hands dirty and having to chase after frightened mobs for a kill. I think definately enh till lvl 50 is the way to go, but after that it's just a matter of preferred play style.

I think part of the reason you never saw another elemental shaman is because you were using the dungeon finder. It seems to try to mix up classes and specs as much as possible. For example, you can barely turn around without stumbling over a ret paladin, but how often have you seen two of them in the same random group?

(Thus avoiding situations like one memorable pre-dungeon finder Stockades group I was in that consisted of my priest, another priest, a third priest, a fourth priest, and one very confused warrior.)

I'm leveling a Shaman as Elemental, and the only time I've had to drink has been in instances.

Then again, he is fully loaded up with heirlooms...

I should point out by heirlooms i just had the shoulders alone, and the potions were the +spellpower and mana regen kind not the typical health and mana pots and i honestly rarely ran low on mana thanks to my water shield and mana spring totem (with seal fo wisdom helping if a pally was in a group), and certainly never out of it during a fight- thats just the big negative i hear about elemental "the amount of time spent regening mana between fights ads hours onto leveling" and it frankly isn't true, i just kept a git of spirit on my gear when leveling and my mana regen was no problem.

-also i did spend a lot of it questing as well and my mana problems and downtime were miniscule compared to the times ive spent on my druids and warlocks ive tried to level in the past.

@ I leveled a lot in the new lfg system and you know what i noticed? I never saw another elemental shaman. not. once.

Doesn't dungeon finder avoid putting two of the same classes together in a group? I leveled Elemental through BC dungeons and respec'd to Resto when I got to wrath. (Got tired of queue times.)

I'd never seen an elemental in my group when I was elemental, but I'd see them when I'd run randoms on the hunter/resto druid/lock/spriest.