This was another fun error message that I received while putting back together my hacked server. This appears when trying to SSH into the Media Temple server through the Terminal Application on Mac OSX.
The solution.
You need to clear the key that already exists in your known host….
perl -p -i -e 's/^example.com.*n//;' ~/.ssh/known_hostsand then you follow that up by regenerating a new key
ssh-keygen -R example.comNow you should be able to access the server through an SSH terminal session and continue the rebuild.