Every SSH server uses a random key to identify itself. When SSH is installed a new key is generated. SSH clients keep track of the host key, if it changes the user can be warned that they might not be connecting to the computer they think they are. Most of the time this happens when the SSH server or the OS are reinstalled.
In the case of the SSH client in Linux, a changed host key results in the client refusing to connect and showing an remote host identification has changed error.
The easiest way to fix the problem is to delete the known_hosts file: