In order to down all the 5 man boss's it looks like Pally is the way to go. There are probably a couple of instances or boss's where a warr just wont cut it, even with the CC from the mages. This here is a great thread about it all...
Warriors suck - I'm rolling a Paladin!

So, the only question I have now is to have 3 mages or 2 mages and 1 lock? Lots of pros for having the lock (soul stone, off tank) and of course having to box 4 different class's vs. 3 might be a pain. What's your thoughts?