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.

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.