"Warning: remote host identification has changed" - ssh client connection problem on Ubuntu

Connection is refused by remote host on you Ubuntu ssh client and you receive the long message with "Someone could be eavesdropping on you" etc.
Actually if you read the message carefully it says what you need to do:

1. the problem is caused by the old RSA key stored locally in your /home/user/.ssh/known_hosts file; message clearly says what key is causing the problem: e.g. "/home/user/.ssh/known_hosts:1"
2. on your system go to /home/user/.ssh/known_hosts and using any text editor simply remove the key