[fmw]

You are correct, of course. Eventually some user would figure out they can rotate "aaaaa" and "bbbbb" every other week to avoid having to remember a better password. That being said, they could just follow up with "ccccc" instead of revert to "aaaaa" (or go through the words of some pop song, which would arguably be a somewhat safer pattern to follow). In other words: creative users will find ways to cheat whatever measure you come up with. The only solution is giving them no choice in the matter and to randomly generate passwords for them, but that opens up another can of worms as they will start writing them down on post-it notes attached to their monitors.

The only real solution is educating users. Comparing to the previous password (provided by the user when changing it) is close enough to the spec to be able to get away with it in most circumstances (possibly combined with saving a history of password hashes, so you can see if people don't repeatedly use the same password).