Once a connection to a remote machine was established 1st time, the identificantion will be written to ~/.ssh/known_hosts. If the ID of a remote machine changes, e.g. cause someone installs it new, you'll get such messages while connecting.
Simply remove the part in ~/.ssh/known_hosts that depends on this machine.
Note that this method of operation is less secure than if you have the option "StrictHostKeyChecking yes" set, which disables automatic addition of host keys to the known hosts files and will abort any connection attempt to a host whose key differs from the one in the known hosts files. Without StrictHostKeyChecking, you are prone to the man-in-the-middle attacks that Kurt made such a fuss about around a half a year ago. Cheers Tobias