Still, this is generally a product of the system, rather than the players; lots of problems with Paladins tends to be alignment systems, which in 3.0/3.5 particularly, you have ONE code of conduct in common. When you've got a seven bulletpoint list of 'Unless you act this way, you become less useful than the Fighter', people tend to play the character exactly how that list dictates.
See this is part of the issue, no one wants to look past the words, and the letter of the law, rather than go with the spirit.
3.x actually got Alignment right. They said it was more of a personal thing, that in the end, how you played it was as important as following it. Lawful Good didn't have to follow unjust law systems. Hell, they could rebel against previously just law systems if the system does more harm than good.
Lawful Good is about Justice, not Law. (The other way around would be Lawful Neutral, which what most of the horror stories about Paladins were. They stuck with the Lawful aspect and completely forgot about the equally important part: Good.)
Hate the game, not the player; if the game didn't punish you for not acting like a Lawful Stupid Paladin, less people would play Lawful Stupid Paladins.
No, in this case it IS the players. Because they heard 'stories' of bad Paladins so they assume, automatically, that all Paladins will be played that way. I spent a good three months destroying that archetype in my first 3e game, by making out at least three separate Gods/esses that had Orders of Paladins, and each had different focus, one was anti-undead, to the point where she commanded her soldiers to seek them out first, among all other evils. Another was anti-Demon/Devil, so on and so forth.
It's kind a like 3.x and then 4e's halflings where everyone immediately assumed that because they weren't fat, useless, cowardly homebodies as per Tolkien that they automatically were 'Kender' and immediately associated the archetype of asshole players to an entire fictional race. Which is ironic as it sounds like they were blaming the game, for player behaviour. Yes, Dragonlance said they were kleptomaniacs, but YOU the player didn't have to play them that way... Because it says so in the book has never been a valid excuse for dickery, no matter what class, race or gender you play.
Because God forbid that someone new, in a game they don't understand, clings to an archetype they find cool and enjoyable.
If they keep playing the same character after several years of gaming, that's when I take issue.