I was quite annoyed at the change from -2 to -3 level. It went against every prior edition of the game.
Since the 3.5 DMG still indicates that Paladins turn at -2 levels, I would guess that someone said "tweak the paladin a bit more" and so someone did - albeit without a thorough playtest/plan.