Then the problem is not "I support an app that uses md5 hashes" any more. Your problem in that case is "all my users accounts were broken."

Right, but you can still perform the migration I suggested and flag accounts for a password reset on next login.