My priest took me forever + 1 year.
My warrior took me decent amount, not to shabby.
My paladin was pretty quick actually.
My hunter was zomg fast.

If I re-leveled a priest I would level it very fast. The most important thing to know about a priest is to get a wand, and wand. Wanding does so much damage and is so good for priest leveling.