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:
This causes the SSH client to forget all the host keys it knows about. Next time you connect, it will create the file again and ask you before adding the new key.
The version of SSH installed in Ubuntu does not produce a known_hosts file that is easily readable. Unless you are paranoid about security, simply deleting it is safe.