They could hash substrings or variations of the new password and check against the original hash. Further, I guess they could be storing hashes of several modified passwords, but that seems unlikely.