My 3x war 1x paladin 1x priest is killing it at level 27. Deadmines and stockades are very easy, the only problem is mobs running away, but I am getting better at that as well.

I'm not leveling at some god level, but I'm on pace for roughly 6 days /played, which I'm very happy with.

As for spec, you should be spamming thunderclap, rend and sunder armor (with some cleave) until you get to 36 and get whirlwind.