A paladin is a better character if you have a high Strength, Wisdom, and Charisma, but it's not necessary. The argument that you need high scores in all three stems from trying to do too much with the character.
The bottom line is the spellcasting potential of a paladin is pretty poor. Compared to his combat prowess and the abilities powered by his Charimas score, spellcasting is the weakest link of a paladin. It might be sacrelig to say this, but Wisdom is a throwaway score for a paladin. Let me justify.
For a paladin, a high Wisdom score really only translates into spellcasting an a moderate bonus to Will saving throws. On the other hand, a high Charisma translates into better Turn Undead chances, better Lay on Hands totals, and a higher overall bonus to saving throws.
So I put a 10 in Wisdom. What do I lose? Spellcasting, yes, which is poor for a paladin anyway. My high Charisma bonus will keep my Will save respectable, and if I'm worried, I can pick up Iron Will later down the line. I'm not as naturally good at Sensing Motives but I'm a master diplomat and if I want to be good at Sense Motive, I'll just take a few more ranks in it than I would otherwise. If I WANT spellcasting down the line, I can pick up a stat boosting magic item and get there in an instant.
Really, a well-designed paladin would do better putting high scores in Strength and Charisma, which means they're no more MAD than a fighter or a rogue in the end.