Warrior works well, if you drive with the warrior.
There are a lot of reaction abilities, which are strong if you use them and make for a weak choice if you ignore them.

The priest has strong single and aoe heals.
I'd go with a Disc priest.
The healing is a bit weaker, but the mitigation of damage offsets this quite a bit.
Disc is probably the best healer for keeping a single target up.
And then you'll have Pain Suppression/PW: Shield vs upcoming damage.
Holy Nova takes forever to drain your mana, which will good for keeping the priest/mages up, or heals on the move.
Mass Dispel is virtually instant, and gets you some fear protection, especially in conjunction with Fear Ward.

Mages are very strong DPS, possibly the highest.
I would go 3x Arcane, as they output a lot more damage then other specs, at least as a boxer.
Frost is a large step back in damage, and Fire is proc dependent.
You might go with 1x Frost for the snare effects, but I wouldn't really consider this with a warrior... possibly with a Druid tank, because you can dual-spec to Boomkin and have a full caster team for things which don't require a tank.
With a full blown tank on the team, you don't really need the control/snare of frost, so I'd go with the higher dps.

Not sure that the team will pvp that well, in arena.
But it should rock battlegrounds - you'll have heals and rez capability, a warrior in the front to take the initial brunt of attacks, 3x sheep and a lot of firepower ranged. Plus the offensive mass dispel.