Well, here's my take:

I run a Holy Paladin and my team is 85 now and almost in all 333 Item level gear (some 346). I have done every Normal instance in Cataclysm and several bosses on Heroic.

Mana efficiency/regen can certainly be a problem at times. Once I hit about 83, it was bad. Really bad. But after getting several gear upgrades it is manageable. Had to adjust my Paladin's healing macro a bit for efficiency (and I'm sure somebody here can give me some pointers to make it even better), but now I can definitely last several minutes on a Heroic boss fight before going OOM. Here is my healing macro:

/target party1
/cast avenging wrath
/castsequence reset=combat holy light, holy light, holy light, holy light, word of glory
/cast holy shock

I have a separate "Oh Shit!" key for his quick heals in case the tank gets REALLY low on health. I also have a separate key set up to cast divine plea and drink a mana potion.

AoE healing, like someone earlier in the post said, just plain sucks. My Elemental Shamen can barely do any healing at all with their chain heals anymore, so I'm actually considering just having them do Healing Surge on themselves when they get low as opposed to the futility of a chain heal cycle.

But thats my take, for what its worth.