Try and do some XP tracking for a couple of hours and see what you get - post it here and you can compare against other boxers and that way you'll find out if you're doing something wrong if you just have to get used to the pace of classic :-)

While the nerf does such, some comps have gotten to 60 with 4 mages and priest, so warrior is not a precondition. I'm only doing RFK at the moment so can't really comment on higher level instances, but I've had no issues just spamming battle shout and ae'ing. Eventually my mages will pull aggro, but not until the mobs are around 40% and it can be healed through. So maybe just do smaller pulls? Usually I just stick to pulls of around 6-9 mobs depending on the special abilities of the mobs.