5 Paladins is a very strong combination and a relatively (and I stress relatively) easy way to go into Heroics so long as you accept just a few limitations. One being, that since they're all melee, you'll be susceptible to bosses who do aoe melee damage like whirlwind. The second limitation being that they're much more dependent one having a good weapon than ranged casters are.

Other than that having done both a 1xPaladin,4xShaman team and and a 5xPaladin team, I found the all-Paladin team to be much easier for overcoming the "all-new-80-with-crappy-quest-gear" hump than I did with the Shamans.