Two better options (both require more work) would be to either
Add the new SALT + Sha256 below the current one, so you are salting then encrypting the MD5.
2) Setup as part of your login a request to reset password prompt upon login. More professional, you would just need an extra column in your passwords to see if they use new or old. And then in your login script use the login script based on old or new..
I guess the question is will your customers believe you, or will they think you have lost their passwords -> loss of business