Doesn't this mean that they are storing previous passwords in plaintext? Surely a massive no-no.
Not really. It means that the system has to store the previous passwords -- not necessarily in plain text -- but not the current password. If the system is successful in ensuring that the passwords are appreciably different then having access to the password history won't significantly compromise the current password.
The password history can be salted and stored using a key accessible only to the system -- or using (say) a hash of the current password -- so it needn't be easily attackable in any case.