Imported customers can't reset password

Question

We imported a list of customers, which contained cleartext passwords from an old database (yes, believe me I understand how terrible it is to think they were stored as cleartext).

After the users have logged in at least once, then the Magento CE 1.9 reset system works like a charm. Also it works fine for new accounts that are created online, or in the admin.

The problem only exists for those that were imported, but have never logged in since the migration to Magento. After they click "Forgot your password" from the Magento Login page, they are asked to enter their email, and after they do, they receive an email with a link to go reset the password.

However, after they enter and confirm their new password, the system tells them that the link they used has already expired. This should not be the case, because I have the link expiry set to a full day, but the error occurs even when completing the process in less than 10 minutes.

Is it a password hash/salt problem? I assume so, since it works for imported users that had previously signed in (therefore correctly encrypting their passwords).