However, these people were not just called later in life; they were often called in their youth, at a time roughly equating to first level. Taing this option away invalidates a very good roleplaying experience, that of the called warrior.
I couldn't agree with this more.
However, I strongly disagree with the notion that Paladins should be opened to other alignments. The truth is, the Paladin fits a very common fantasy archtype. The Superman-esque (in terms of morals) uber-good, protecter of the weak and upholder of Just Authority-type. This is an archtype that has been tapped time and time again, down through the ages.
And being god-chosen is not enough. He must be good. And he must be lawful. It's *part* of the Archtype! What would Superman be if he suddenly developed a CG bent, and hated authority? Well, he'd be a lot more like Wolverine (to keep the comic book analogy). But, while both those are important archtypes (the chaotic loner who fights for good, and the lawful authority figure who fights for good), they represent very different things.
And, yes, you might argue that the Paladin is a psudo-Christian Crusader. But let's be honest - you could much more easily argue the monk is setting specific. After all, with only minor changes to his code, a Paladin can represent a Samuri in a eastern setting, but there is *no* monk-like western archtype.
And the samuri is a good example of what I'm talking about. The Paladin is not some random class. It's a VITAL archtype found is every culture - whether you call him a Paladin or a Samuri or whatever. I like the flavor of the paladin just the way it is - Lawful, Good, and a core class that felt "the calling" from an early age.