I believe that I would allow a re-roll. I agree that you can play with the following stats, but you would be lacking things for a Paladin. The suggested stats were...
Str 14, Dex 8, Con 12, Int 10, Wis 14, Cha 16
The problem with this is that the AC would be very low... something that you can't afford in a character that is always going to be in the front line.
Str 14, Dex 10, Con 12, Int 8, Wis 14, Cha 16
I believe that this is probably the best build given the stats... but a Dex 12 is very nice to have for the AC, and with Int 8, you would get just one skill point per level... pretty hard to develop more than just one stat so you would have to pick between ride, diplomacy, and whatever else would be nice like sense motive and move silently. Wisdom and Cha are fine... but I like to move Cha up to 18 or higher for the Paladin and a Str 14 will hurt more later on.
Str 16, Dex 12, Con 14, Int 8, Wis 10, Cha 14
This build might work, but if you plan on giving up spells, healing, and saving throws, why play a Paladin at all? It would be better to go with a fighter. (I realize that you would still have a +2 for some healing and better saving throws, but Cha also affects diplomacy, and turning undead)
So, in conclusion... I would say that the rolls allow for a playable Paladin. But the Paladin will have to choose between being a sub-par fighter, having no skills, being a poor spellcaster, turning not being an option and having less than optimal saving throws with little healing power. Paladins definately aren't overpowered even with awesome stats. I would give them better stats so that it is more fun to play.