Caster classes have it a bit rough at first in Outland. Unless you were running raid instances for gear before hitting Outland, you probably have very little spell damage. But as you work your way through the Outland quests and instances your spell damage starts to increase pretty fast.

Paladin + holy priest + 3 DPS seems to be a good setup. Paladin can keep aggro on several mobs rather nicely, and as the DPS gear up they're able to burn stuff down faster and faster. My paladin/priest/hunter/mage/warlock team did well on the first two Ramparts bosses, but managing three separate DPS classes was a bit inefficient. I'm leveling up a paladn, priest, and three hunters now.