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_hosts
and then you follow that up by regenerating a new key
ssh-keygen -R example.com
Now you should be able to access the server through an SSH terminal session and continue the rebuild.