I have just finished leveling a new Horde team and I went with Pally, Warlock, Mage and 2 Shamans (1 dps and one resto). As a point of reference, when I dinged 80 by 50/50 dungeons and questing so I had a lot of blues but I was able to clear gundrak straight off with this team.
I love the mage for dps and food and I love the warlock for summoning and also they put out a lot of dps too, 2 shamans are nice to have for anti fear etc (not as good as 3 but close)
Just my 2 cents