The reason why shaman work better with paladins is this:

Paladins benefit from EVERY SINGLE shammy buff. Melee AND spell.

Furthermore, Paladins have this uber buff known as Blessing of Salvation. If you're fine on threat, they've got this other buff called Blessing of Wisdom. If someone pulls major aggro anyway, there's a BoP.
Warriors don't buff elemental/resto shaman except for Commanding Shout.


The synergy is just so much better between pallies and shammies. I started out with a warrior tank and switched to my pally for a reason. Not saying that pallies are better tanks -- warriors certainly have their niche and much better avoidance for boss fights. Warrior single target threat is far superior. I'm not saying that warrior tanks won't work either. It's just you can't just focus on the tanking alone without also taking into account the buffs shammies bring to pallies and the buffs pallies bring to shammies. And that's where that group composition really shines, honestly.