Are other users still able to login ie does it just affect one or some users?
Does registration and subsequent login work?
try adding this to user.config and then touch web.config:
<add key="CheckAllPasswordFormatsOnAuthFailure" value="true" />
if login fails after that try manually updating it in the database in mp_Users, type in a clear text password and then try again, the above config setting should then let you login and it will automatically encrypt the password that you entered as plain text.
If your machine key changed it will affect all users and there will be no way to recover their passwords with a different machine key so you would need to reset the passwords on all users if the machine key is not correct for any reason though you may think it is restored this problem should not happen if it was restored.
I assume you are just seeing the "login failed" message and not something else like locked out.
Hope that helps,
Joe