[notlostyet]

You can also just hash the existing hashes. bcrypt(salt + old_md5). New passwords can use a new MD5-less scheme.