I found an interesting entry in Tobold’s blog which comments on the paladin’s melee problems.
“…from all what I read paladins trying to tank with protection spec or deal damage with retribution spec find that they aren’t very successful and nobody wants to play with them.”
The paladins complaining don’t know the class well and expect to do things that the class is not designed to do.
Yes there are holes (ie retribution tree) but like every class there are certain builds that make the class work extremely well. Which is why a large population of paladins are Holy.