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.