OK, if you have been moving things around your world, sometimes, you will do a ssh myserver and you will get a public key does not match, could be a man-in-the-middle attack.

Well, this could be it or it could be that you've just rebuilt your network. If so, then you need to remove the host fingerprint from the ~/.ssh/known_hosts and you can just use (unintuitively) ssh-keygen -R <hostname> to do that.