An arena team in most cases is just what you can get, but if you're working for an ideal, then it's poor to take two of anything. Variety is the key.
Arms Warriors are not massive damage on the high end, they're very solid damage with some fantastic utility and obviously the most important PvP debuff in the game. Taking two of them, however, is a waste if you got other opps. One is a must have, though.
Holy Paladins are durable, but they have ZERO utility of any form outside of a few cooldown possessing buffs, 1500 stuck Hunters and Rogues might cry about their "invincibility" but they're actually the easiest class to totally shutdown due to the total lack of instants.
I would suggest a Holy Priest in place of one. Shields, Mana Burn, PoM, Renew, Dispel, Mass Dispel. If not a Holy Priest, then at least a Restoration Shaman. You need SOMETHING with Dispel/Purge.
Frost Mages are fantastic to bring along, one of the most durable classes to bring to an arena, any other type is simply dangerous. Hypothermia goes to 45s in the next patch, I'd rather take that over the coals SL/SL Locks are gonna be drug through when their leech effects are halved and their shadow school is perpetually locked out.
Just try not to take two of anything, that's a problem that has given us some struggle. We don't really pick and choose our members, just take what we can get.
Our original team was 2x Holy Paladin, 2x Arms Warrior and a Frost Mage. The lack of dispels and the lack of inter-class utility caused a lot of problems. We did ok, being good players and being solidly geared we settled between 1800-1850
Our team then changed with folks quitting, etc, to 1x Holy Paladin, 2x Arms Warriors, 1x Frost Mage and 1x Elemental Shaman. An awkward 4 DPS team, but it's moved us up to between 1950-2050 week to week while we still adjust, but it would be so lovely to have one more healer or more variety in the DPS rather than two Warriors
If you're going to stack two of anything in an Arena team, Paladins and Warriors are the worst choices, and Merin did a fantastic job outlining why Paladins are a poor choice if not supported by a Priest or Shaman. I have seen two Hunters, believe it or not, succeed on an Arena team. They used a Shaman and a Paladin with two Hunters and a Mage. Doesn't sound like much of a team, but one was MM/Surv and one was BM, and they were quite deadly, as I didn't have a Paladin on my team at the time for BoP, I died very swiftly. Intimidation with Imp Concussive Shot... It was bad.
Just think about that team... Each Hunter has a pet, one scorpid and one windhawk silencing thing, and then the frost Mage's elemental. It's frontloaded DPS without seeming like frontloaded DPS and it takes you by surprise.
Anyway, I wouldn't predict much success with 2 Paladins, 2 Warriors and a Rogue or Mage. Switching just one Paladin for one Priest and one Warrior for a Hunter (a class I have always liked in Arena), and you're working on a successful team.