we changed to stronger password encryption in version 126.96.36.199, but it was designed so that it would not break existing user accounts, it will try the old encryption if login fails and then if the old encryption works it will update the same password to stronger encryption.
Lots of people upgraded and I'm not aware of other people having any major problems with it so I have no idea why it is not working for you unless your machinekey changed in web.config.
For new installations starting with version 188.8.131.52 we do automatically update the machinekey to a new generated one but this should not happen for upgrades unless you added this to user.config:
<add key="TryEnsureCustomMachineKeyOnSetup" value="true" />
if that is in user.config and it detects the default machinekey then the setup page will try to update the machinekey to a new one.
but we don't ship a user.config file so it should not happen to upgrades of existing sites it should only do that on new installations when the ms web platform installer creates a user.config file by copying user.config.sample as user.config.
If somehow that happened to your site (ie if tha is in your user.config) then it means you were using the old default machinekey which is not secure.
You could remove that setting from user.config and then restore the old default machinekey:
<machineKey validationKey="55BA53B475CCAE0992D6BF9FE463A5E97F00C6C16DA3D7DF9202E560078AB501643C15514785FEE30FEF26FC27F5CE594B42FFCA55452EF90E8A056B4DAE9F39" decryptionKey="939232D527AC4CD3E449441FE887DA110A16C1A36924C424CBAAE3F00282436C" validation="SHA1" decryption="AES" />
that would make old accounts able to login but would break accounts that were already upgraded and it would not be secure. If a hacker knows your machinekey they can hack your site and gain administrator access so it is very important to use a unique custom machine key.
I don't really have any other ideas to help you. If you kept a backup of the site files and the database you could go back to your previous version by deleting the files and restoring the files and then restoring the database from backup.