Got this when trying to connect to a Windows 10 Technical Preview using Remmina after a Windows upgrade.
Somewhere, somehow the key must have changed.
I fixed that by deleting the freerdp known_hosts entry.
Remove the host entry for the particular server.
When trying to reconnect it will ask you to re-authorize the host.