That's not practical. Password hashes should be slow, to stop dictionary attacks; and it's easy to imagine a couple thousand "similar" passwords (flip case of some characters? 256 possibilities for an 8-character password. Add year of birth? 20-50 possibilities. And so on.)
Presumably the ratio between the rate of normal logins (each of which requires a single execution of the password hash) and the rate of password changes is at least a few thousand.
Sure, but if you run through a few thousand hashes to check for similarity, an attacker can check for the couple thousand most popular passwords in the same amount of time. It is possible to throw enough money at it to make an attack uneconomical, but that's expensive.
(Also, DoS. Note that you can't stop people from changing passwords when the system is under load, as that sets you up for a combined compromise-password-hashes-then-DoS attack...)
