Connecting to my Windows 2012 R2 server (but the same applies to Windows 7 machines) with RDP using Remmina periodically fails with error “Unable to connect to RDP server MYSERVER”

One solution is to get rid of the fingerprint of the corresponding remote host. Edit freerdp known_hosts file

vim ~/.freerdp/known_hosts

or, on a recent Ubuntu system,

vim ~/.config/freerdp/known_hosts

and delete the offending host key (the line in corresponding to the IP/hostname of your server) you are trying to connect to and… voila!