MD5 is not so broken that you can de-hash all the passwords easily, but assuming the quality of the passwords isn't too good then you could probably brute force them and convert them to the new, more secure format. The brokenness of MD5 results from it's relatively small length (more collision surface) and it's computationally simple calculation (meaning brute force attacks are more feasible than algorithms that have larger run-time complexity such as SHA2)
If I were you I'd do both methods you listed (because as you mentioned, getting the passwords moved over quickly is important in case your DB is hacked). First I would brute force all the brute forcible MD5 passwords and convert them to the new format. I have done this in the past, and by far the best results have been using HashCat (the Cuda or OCL flavors preferably since they use the GPU and are 200 times faster). If Hashcat is too difficult (the learning curve can be steep), then try John the Ripper. It is a lot slower than HashCat but it's a lot easier to use.
For the passwords that you can't crack, expire the user's account and have them reset the password. Or to be nicer to your users, just update the password in the database to the new format the next time they log in by sending both hashes. If the MD5 checks out, then destroy it and replace it with the new format. These are just some ideas.
EDIT:
Forgot to mention that if you want to just hash the MD5 passwords into the new format that would be just fine security-wise, though it adds another layer of complexity to your code, and where there is complexity there is room for implementation flaws. Just something to think about.