I'm currently running paladin + 4x elemental shaman and I love it. Just blast through everything and the pally holds aggro like a champ.

My other team is a heavy dps team, 2x shadow priests 2x warlocks. It's fun in pvp, but other than that it's kind of a gimmick, I can't do any serious pve especially without a tank, and there's no arena viability at all.
I think other teams run into similar problems, like the all mage teams. However, it's all about what you want to accomplish.

I went with shaman because I can blast through the instances with elemental, have viability in pvp, and with the paladin be able to do any 5 mans I want.