I have a number of connections that I have set up in Remmina Desktop Client and today, suddenly one of the connections stopped working with this message:

After checking all the usual things such as the validity of my credentials, I found that it was to do with the server certificate and my client having somehow come adrift.

Here is the solution.

Edit this file:

~/.freerdp/known_hosts

find the ip address of the misbehaving server and delete that line.

I restarted my rdp client aswell, just to be sure.

Hey presto! You will be invited to trust the new server credentials.