I recently set up ssh on my linux mint server. I wanted to change the password on it because of security reasons. I followed this guide to change the password. The password was successfully changed, and I know because if I want to change it again the 'old password' is the one I changed it to. However, when I try to login, the new password is denied, and the old password is accepted. Any help appreciated!
There are two authentication methods at play here: password-based and key-based.
The guide you have linked to provides instructions to change the passphrase, which only affects key-based auth. As noted in the guide, a passphrase is used to add another layer of protection to an SSH private key. When you change a passphrase, the change occurs on the client side.
If the server does password-based auth, you would see no difference. Passwords are authenticated on the server side, against a user directory of some kind. This can be the default /etc/shadow file, or something more complex such as an LDAP server.
ssh -vvv will help diagnose this. The debugging output will show the list of authentication methods that the server accepts, and which one is currently being used.