In my games I solved the Paladin problem with two simple changes. First, Paladins are only required to be Nonevil and are not required to be Lawful. Second, I require paladin players to outline the code of their specific knightly order or their personal code if they don't belong to an order (In my game world, paladin-hood can pass on through inheritance or by undergoing the sacred rituals known by certain holy orders).
I now have two VERY different and interesting paladins; one Lawful Neutral and one Neutral Good.
Problem solved.
