I would argue that a class needs something unique. Why should I play a paladin as opposed to, say, a fighter/cleric? I would argue that your fix fails to address the paladin's biggest problems.
- MAD
- Smite Evil doesn't have enough effect and isn't usable often enough.
- All the class features are concentrated in the first few levels, leaving little incentive not to multiclass out.