Why not use lazy rehashing? On login, the password is availible and so can be rehashed properly.

You can do better - if they're storing MD5s of the passwords, all they need to do is hash those again with another salt:

    BCRYPT(MD5(Password))

Running BCrypt or SCrypt over the current MD5 hashes is easy, and they can do it right now for every password. If someone (else) grabs the database in ten days time they get no MD5 hashes of passwords instead of half of the userbase.

I believe the legacy api required md5(md5(password) + time) or something like that. Which means they needed to store the md5 of the passwords or modify all third party clients that used this method.

Mainly because many Last.fm scrobbling clients relied on the legacy API that uses a person's password as a private key to authorize requests.

They send a token hashed with the password and they have to keep the original md5'd password on file in order to allow these clients to work.