As mentioned in another comment, I'd probably do a Levenshtein distance between the old and new passwords, and reject if they crossed some threshold. However, only knowing the plaintext of the immediately-preceding password as they enter it to authorize the change, it wouldn't do much to stop them from doing:

PasswordA SomeOtherPassword1 PasswordB SomeOtherPassword2 PasswordC SomeOtherPassword3

Just iterate on every other change, and you've beaten the requirement.