That doesn't mean that they're storing your passwords in the clear. They could simply be keeping hashes of your old passwords around and checking simple variations of the new password you're trying to use.
I think many people are misunderstanding what you're saying i.e., they think you're saying that similarities between hashes correspond to similarities between passwords.