You try to ssh to a server and you get "Host key verification failed". What does it mean?

It means that the key of the remote host was changed and doesn't match the one that stored on the machine (in ~/.ssh/known_hosts).