Ideal solution, I think, would follow the following process:
1. User attempts to log into system.
2. System hashes password+salt with new method, compares to stored hash. If match, permit entry. Else, go to step 3.
3. System hashes password+salt with old method, compares to stored hash. If no match, deny entry. Else, grant entry and go to step 4.
4. System generates newsalt. Hashes password+newsalt with new method, replaces existing stored salt & hash data.