I have an ESX box which I have loaded with two Ubuntu Server machines.
During setup, I chose no additional packages to install as I just wanted a lightweight machine for testing.
The first thing I did was change the root password via sudo passwd
After ESX got on my nerves through lag, I decided to install OpenSSH via apt-get install openssh-server.
It did it's business, and I then opened putty and could connect in to both machines fine. The first time it connected, it asked me to add the ssh key as obviously it did not know it.
Anyway, the second server is working flawlessly, but, the first seems to be giving me trouble.
I was in the middle of typing a sentence when it kicked me off for no reason and when I tried to reconnect, putty gave me a warning that the ssh key had changed and it is potentially dangerous. I attempted to log in anyway and it did not work, just the standard access denied message.
Using the second machine, I SSHed in to the first machine and it worked straight away, I then killed the SSH sessions (and possibly SSH server), I then reconnected via putty and I again received the security warning message, but, it allowed me to log on fine.
... I thought "glitch" and nothing more of it, but, it just happened again!
I really do not understand this and was hoping someone here can help?
The most likely explanation for why you were kicked off of one of your virtual servers, and why you were warned that its SSH key had changed, is that the server's IP address changed. This would have resulted in it going down for a short time (or, if you're using DHCP, was perhaps the result of it going down for a short time). That is, either the server went down, or, more likely, just its network connection was interrupted. This would have interrupted the SSH connection in progress and also could have resulted in the IP address changing so that when you tried to connect to the same IP, you would have been connecting to a different (possibly virtual) machine (with a different SSH key). Or, so that when you tried to connect to the same machine with a different IP, you may have been connecting to a machine whose IP was the same as the IP address of a machine the client had previously connected to (which would give the same error about the SSH key changing).
For me, it looks like you are using an IP address that is already in use in your network by another SSHD enabled server. It could explain you being dropped and when you reconnect, putty complains about the key changed. Please check it.