“Your password is too similar to a previous one”

I don’t know too much about salting, hashing, and encryption, but it always upsets me when I see a “Your password is too similar to a previous one” message like this, because I assumed that whoever was showing this message was storing my passwords as plain text somewhere. This thread on Twitter, started by Anna Filina, addresses this topic.