Comment 3 for bug 41738

You also come across that error message when you have several SSH servers on different ports behind one IP.

The only way I found to temporarily handle that problem is to empty /home/user/.ssh/known_hosts and chmod 000 it.

This way, you always get prompted by nautilus as if it was the first time you were connecting.

Not the safest workaround.. subject to man in the middle attacks if you're accepting SSHv1 and allow password authentication.