The ideal solution is to get a copy of the site working as it was before the upgrade and then change to cleartext passwords then do a query to join the new db with the old copy and get the original password and put it in the new db in the pwd field of mp_Users and set the password format field in mp_Sites as cleat text (0 I think). Then finally generate a new machine key and change back to encrypted from site settings so it will encrypt the clear text passwords again with the latest encryption and machine key.
It is extremely important to use a custom machine key, if someone knows your machine key they can easily hack your site no matter what password format you are using. This is why we added security advisor.
Note that somewhere along the way we changed the encrypted passwords to use a stronger encryption with salt and to do that we migrated password to the newer pwd field which is large enough for the stronger encryption. I don't know if this was before or after your previous version.
Even if you decide to reset the passwords then you should first change the password format field in mp_Sites to clear text, you could then run a query to make the new password something like the email + changeme, there is also a new flag to MustChangePassword on mp_Users. There is no way to generate encrypted password with just sql so you must first reset to plain text passwords and then change to encrypted from site settings so .NET code can generate the encrpyted versions and salt.
Then I guess you could email or tell your users to recover their passwords with password recovery and after the y login change it to a new password.
Hope that helps,