My ssh connection to some Amazon instances stopped working after I moved around the elastic IP. I got a “Host key verification failed” error. The following fixed the problem.

ssh-keygen -R  servername

This removes the offending entry from ~/.ssh/known_hosts which was apparently causing ssh to fail.