I agree with many here that they need to bring back the link to divinity. In our modern world, morality has become very subjective because everyone disagrees with how to define "good". Good has become subjective. But in the BG world, deities actually exist and have their own views of what is "good". They give the paladin power as long as the paladin adheres to that definition. So there is nothing logic breaking having an "evil" paladin following the teachings of an "evil" god - they are just following the god's wishes. There is no logical or moral ambiguity.
However, I think the game should warn the player when they are about to make a oathbreaking act. The paladin should know when an action is against their god, so the game should inform the player and let them take it back. In other words, the paladin would be a greater authority on the topic than the player, so the player should be given the information.
In summary, two small changes make paladins work: align them to the teachings of a deity; and provide in game warnings of oathbreaking.
