The best approach is probably to disable the account completely until an interactive login is made and a password reset can be forced but some would be up in arms about the inconvenience caused: you can't just allow a simple reset as the login could be coming from an attacker not the original user, an extra channel will need to be used to verify the identity. You might just have to leave the account locked forever and expect the user to create a new one - but now you have the old account and its content which may be used as a dependency of many projects which now break, unnecessarily if there hasn't been a login by a nefarious type.
You wouldn't lock the account forever, the point is to establish that the person whose password was compromised knows, that the password is not the only factor which is used to regain access to the account, and to ensure that your service (rubygems) and its downstream users are not compromised as well as a result of the breach.
Any groaning about the inconvenience caused by disabling account access until the password is changed, can be simply shrugged away in favor of security concerns, with a link to this story about rest-client.
By the time you have learned the user's plaintext password, their account may already have been compromised. There's a case to make that you disable all downloads of any gems that might be compromised from the account until you've verified they aren't. That might be over the top, especially for popular projects as now we are talking serious inconvenience affecting potentially thousands or more of downstreams.
It's a sticky situation, since you don't really know how long that password has been in the open for hackers to use and abuse once you've discovered it in a password dump.
(source: I work for Heroku Support)
RubyGems has a responsibility to its users and community here. It (like npm) needs to take this stuff seriously.
But simply forcing a password change at the next login after detecting an insecure password would not unduly burden anyone and would be better than doing nothing.
Sometimes you have to have your priorities straight. If you found the password, someone else can find it.
The only time you would have access is when the user logs in, so for rarely logged in users you would have to proactively reset their password or cross your fingers.
But even with 12 round bcrypt hashing, you should be able to fairly cheaply attack a list of 2,000 bcrypted passwords with a million-entry database of leaked e-mail/password combos in a GPU-month.
Probably easier to force a password reset on everyone and then do the checking on password change, although you need to be careful there not to be sending the password.
EDIT: uhm, wait, so if you've got the e-mail address in the dump then there's only one user for that, so just grab their salt and hash the password and check it. So that million entry database should be checkable in a bit over half an hour...
Wasn't challenge/response / SRP authentication debunked ?