It seems there is a cache problem on my computer or something. I changed my password with the Users and Groups tool and it seemed to work, the keyring manager asks me for the new password. However, when I log in with the new password it tells me authentication failure, but still accepts the old password. The same result for using 'sudo <anything>'. This seems like a pretty big security issue..
I should mention I am using 64-bit Linux Mint 8. Also, when I try to change the password again, it hangs on checking password... indefinitely when I try to use my new password.