You could require users to enter their old password when changing it. That way, you can compare two plain-text passwords without the need for plain-text storage (or pre-computing, like other commenters suggested).
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).
Actually, I think there is a technical solution. Say that the password system keeps a complete history of a user's plaintext passwords, stored encrypted using the current password as a symmetric key. Administrators cannot access this password list without the current password.
When a user changes his password, he enters the current password and a proposed new password. The system uses the current password to decrypt the list of previous passwords. It checks the proposed password against the list. If accepted, the old password is added to the list, and it's encrypted using the new password and stored.
Are there any threats against this scheme, or will it work?
Unfortunately, it can't be extended to make sure that the new password isn't similar to the password from two generations back.