In light of recent events, I thought it prudent to change our password storage to use bcrypt hashes. Salting md5sums isn't the worst thing you could do, but it's really not as great as it might seem at first blush. Salted md5s are the leather jacket of bullet-stopping apparel: demonstrably stronger than your plaintext cotton T-shirt, but nevertheless insufficient for the task at hand.
Converting a production system to use bcrypt requires a few steps and some sleight of hand. We can't encrypt the plain passwords because we no longer have access to them. Instead, we could use the md5 with salt as a first pass and apply bcrypt to that value.
The process goes like so:
That wasn't so bad, was it? Step 3 even gave you a little first-hand demonstration of one chief bcrypt feature: it takes a long time to generate all of those hashes. No one will be brute-forcing your user base any time soon. Just don't forget to properly secure your old backups... which you have, right?