What were they using to hash passwords? sha256? I actually am curious since they didn't mention it in their email.
Which is so frustrating. When you upgrade your hashing algorithm, always always _always_ immediately remediate the weak hash mess by hashing your weak hashes with your new stronger hash, and turn the login check into
bcrypt(sha1(user-entered-password)) == stored-bcrypted-sha1
you can then upgrade them to a straight bcrypt if the check succeeds, but keeping the weak hashes on disk indefinitely until the user logs in (if ever!) is such a risk.