My thoughts on "fixing" the paladin will depend very much on what you think is wrong with it.
If you think that it's not powerful enough, adding extra feats or other special abilities may help, although it does step on the fighter's area of specialty. On a more practical level, you might also want to check with the people in your group that don't play paladins whether they feel a revised paladin character will overshadow theirs.
If you think Remove Disease is rather boring, you might consider adding feats that allow a paladin to do other things with that ability, as suggested by Zappo.
If you want to give paladins more options, perhaps you could give them more abilities to choose from, but tie each ability to a thematic oath.