SSH connection problem with “Host key verification failed…” error

"Host key verification failed" means that the host key of the remote host was changed.

Ssh stores the host keys of the remote hosts in ~/.ssh/known_hosts. You can either edit that text file manually and remove the old key (you can see the line number in the error message), or use

ssh-keygen -R hostname