I'm still debating wether to go with paladin, resto shaman, 2 elemental shaman and druid, or to go with paladin, resto shaman, elemental shaman and warlock. My reasons are as follows:

Paladin: With the recent changes to tank mechanics post 3.0 it looks like all tanks will be able to AoE and single-target tank effectively. The more important point, for a boxer, is obviously which tank requires less micromanagement and the answer still seems to be paladin, especially with the 3.0 abilities nicely fitting into a rotation. A blue statement was made that the fights should be more about "moving and healing" than about a threat game, so mobility looks like it will be a bit more important.

Balance druid: With the coeff nerf in 3.0, a balance druid (with earth and moon) will be a very nice (almost mandatory) addition to a shaman team. Warlocks will be able to supply the same debuff (CoE) though.

Resto shaman: This is mostly a matter of convenience. I already had a shaman I didn't use, so I might as well respec it to a healer instead of levelling a new healer. If I had the option to choose freely (ie. the time and the energy) I'd go for a priest due to mobility, but shaman healers have their advantages also (more totems :-D).

Elemental shaman: An elemental shaman looks like a good addition to any team. ToW is a very nice group buff and even after the 3.0 changes, shaman still stack better than most classes (grounding totems, large selection of totembuffs). Damage output is decent and with the option to throw in a backup-heal in case of emergency.

Warlock/elemental shaman: I haven't quite decided on this yet. The warlock can bring some very nice debuffs to the team, but are a bit harder to manage. Added CC in form of banish is situational, but very useful, especially since there's already 3 options for "normal" CC in the team (2 x hex + root). Also adds AE capability, which seems to be the shaman sore spot at the moment (druid has some AE also, but some of it needs to be mouse targetted).

Adding the warlock and removing an elemental shaman removes 1 grounding totem, meaning there's just a single grounding totem left (assuming we use WoA). However, with a warlock, I get better use of dropped gear, ending up with 1 cloth class, 1 leather class, 2 mail classes and 1 plate class. I guess it's in favor of the lock at the moment, but it's still undergoing consideration.