funny i had the opposite experience. i left my locks on a hill in the southern barrens and leveled a rogue to 19 in one evening of playing. Then again, dual firey enchants giving way to dual lifestealing made me rip through things faster than my warlocks...however a few things to note- i only do 3 toons at once so maybe 5 is faster, the enchants with slice and dice make you OP for low level PvE and it evens out in the 40's (for the most part, dual mongoose is nice but not i'm not doing that), and i don't do gathering quests with the boxed teams so i could complete more quests.

i found leveling to the 40's to be very fast, and i stopped for PvP trinkets along the way. now that i'm in the 40's it's getting slower. i'm thinking of leveling 2 druids for some stealth group ideas i've been having too

of course it's all subjective, i just like having my opposite experience. solo rogue that no one can see or bother and then three locks or mages or 2 priests that everyone notices, and even reports haha...i bounce back between the two.