If you want to run dungeons, its probably easier to have 3x Ranged DPS than 3x Melee DPS.
Just about any healer and any tank will work, but many favor the Paladin as their tank; similarly, the Pally seems to have the worst AoE heals.
If you're going with a caster team, an Elemental shaman is a huge boost.

If you want to run PvP play...
The current strong team is 4x Death Knights (Frost, usually), with 1x Healer (sometimes a Priest, more often a Paladin).
In Blood spec (across the board) or 1x Blood and 3x Frost, along with the healer... most instances are doable with this composition.

The fewer classes you have, the easier they are to run in general.
There are less things to manage.
That said, more diversity can be stronger for PvE... assuming you can manage it all.

I'm a huge fan of the Druid composition.
The class can be Tanks, Melee DPS, Caster DPS, or Healers; Paladins can fulfill three roles (DPS, Heals, Tanks), but are not effective ranged DPS like a Druid can go Boomkin.
In the expansion, Feral (Cat) and Bear will be separate specs; currently Melee DPS and Melee Tank is the same spec.
Boomkins need to manage their Eclipse mechanic, which can be a bit of a pain.
5x Ferals is a rather fun composition for PvP, although the Pally/DK's has been stronger this season so far.

The 4x Shaman + 1x Paladin is a decent group.
You could drop 1x Shaman for 1x something else... say a Warlock for the percentage spell power boost.
Three Elemental shaman are more than capable of healing five-man content.
If you want to PvP with the same team, dual-spec the Pally to Healer and then run with Casters.
You could run 4x Shaman and 1x Druid too... same deal.