Paladin is frustrating by nature, the same way a well played Druid is, more cheesy of course, but that's how it goes.
Paladin IS one of the better support classes, that's all they are in groups, both PvE and PvP, to the point where it's not even viable to use a 2H weapon. It's soloist nature comes by default simply due to it's survivability, but at the same time Paladin takes FOREVER to kill things.
Yeah, a Paladin can take down mobs several levels above himself without much fear, but a Rogue can cleave 5 or 6 equal level mobs in the time he takes to do so.
It's overpowered cries come from the fact that it is easy as heck to play, and a little cheesy by nature. But how can a class that lacks any form of: Utility, crowd control, DPS, area effect (consecration = gag), ranged or escape tactics be that overpowered? It isn't.
The class makes a solid offtank when spec'd right, and an armored but far lesser Priest/Buff machine in a party. That's it, period.
In PvP, just because it wears Plate doesn't really mean it's difficult to kill, 6 of the 9 classes in WoW are casters after all, to which all that pretty armor doesn't do jack.
Like I said, all you're fighting is time. Only Warriors and Warlocks have consistent problems with Paladins.
As far as Priests go. There's no class that can successfully counter a well played Shadow Priest. And they're hardly frail.
By default with self-buff they have more armor than a Rogue, and between the godliness of Imp. PW: Shield, Fear and their natural ten tons of healing techs, smart ones aren't exactly easy to take down.
I don't know why you mention Paladin along with it, simply due to the fact that you have to be a pretty crummy Shadow Priest to have issues with Paladins, IMO.
Anyway, concerning Paladins, yeah, I'd love to purge our server of the ten tons of crummy non-support Paladins. And yeah, they're pretty cheesy. But for the sake of general balance and for supporting the handful of well-played, enjoyable to group with Paladins, the class doesn't need nerfing.
It's getting it's ridiculous SoTC toned down drasticly tommorow and they fixed BoL cheesyness, and that's all it really needed as far as I can remember.
Mage, Priest, Paladin, Shaman, Hunter, Rogue. These are all fine, and outside of bug fixes, should be mostly left alone.
Warrior, Warlock. These need buffs and bug fixes in pretty solid quantity.
Druid. Alter cat form and it goes right into the top.
