So I started googling and after a while I found the very simple solution to this problem.
After updating the computer my SSL certificate had been changed, which resulted in Remmina trying to authenticate itself with an invalid certificate/key.
When Remmina tries to connect to the Win PC it it uses the stored key in the file ~/.freerdp/known_hosts for authenticating itself to the remote computer.
Editing this file, by removing the key associated with the computer I tried to connect to, forced Remmina to ask my permission before accepting the other computer's key.
Steps to fix the problem:
- Open the file: ~/.freerdp/known_hosts
- Delete the key entry for the remote computer
- Connect to remote computer by accepting the remote cert/key.
Very simple to do but unfortunately just as simple to forget.