The message means that the SSH key for the server you are trying to connect to has changed since the last time you connected there.
If that server was re-installed (or got its keys regenerated for some reason), all you need to do is edit your
.ssh/known_hosts file and remove the offending line (the one that mentions that server). Make sure you check the key signature when you reconnect before you save it when SSH asks you to.
If the server was not touched however, you have an issue: your
.ssh/known_host was corrupted somehow, or the server was compromised, or someone's trying to mount a man in the middle attack.