SSH will record the public key of every computer you have accessed in ~/.ssh/known_hosts. When you access the same computer again, OpenSSH will verify the public key. If the public key is different, OpenSSH will issue a warning to prevent attacks such as DNS hijacking. This is what has been causing me to be unable to connect to my MySQL through SSH.
vim ~/.ssh/known_hosts
You can see the records of the connections made through SSH, with each record on a separate line starting with the IP address. It is easy to identify the problematic server IP and delete that record to establish the connection.