my two cents worth on your team selection.

pally + 4 shaman is a very good classic team. they do heroics just fine. I have a team of them myself and love them.
everyone can heal, everyone can dps, everyone can rez and shaman can self rez giving you 4 chances to have a team wipe and not run back.
you could swap one of those out for a druid or a warlock to boost the team dps.
the druid can still rez and heal like the rest and the warlock could soul shard one of the team ( warlock soul shard rez it limited to every 30 min )

A less classical team is 5 pally, the leader being protection and the rest Ret.
I'm not sure how good they are at level 80 heroics yet since I'm only 73 but I just did nexus and had a much easier time of it than when I had tried it with 1 pally and 4-shaman.
with 4 ret pallys you can repentance 4 of the mobs and wake them up one at a time and kill them.
the play style is completely different and it takes a while to get used to.