Cannot connect to windows remote desktop by remmina from ubuntu 14.04

The certificate needs to be added to your Local Computer's "Trusted Root Certification Authorities" store. Adding it to the user's "Trusted Root Certification Authorities" store is not enough! If this sounds confusing don't worry - it is.

If you think you already installed the certificate, skip to "Move Certificate on Client."

Export Certificate on Server

First the certificate needs to be exported to a file. On the server, i.e. the computer you'd like to connect to:

1. Run %windir%\System32\mmc.exe
2. Menu File -> Add/Remove Snap-in...
3. Select Certificates -> Add > -> Computer account -> Local computer -> Finish
4. OK the Add or Remove Snap-ins dialog. The console should now contain Certificates (Local Computer).
5. Select Certificates (Local Computer) -> Remote Desktop -> Certificates. There should be a single certificate with your computer's name.
6. Open the certificate.
7. Open the Details tab.
8. Copy to File...
9. Select any format, e.g. DER encoded binary X.509 (.CER).
10. Type in any file name, e.g. <computername>.cer.
11. Copy the file to your client computer.

Another way to get the certificate is to follow steps 6 to 10 on your client computer, on the Remote Desktop warning dialog mentioned in the question. But you're trusting the network in this case. At least compare the fingerprints, so you can be sure you trust the right certificate.

Import Certificate on Client

On the client, i.e. the computer you're connecting from, an receive the warning popup, do:

1. Run %windir%\System32\mmc.exe
2. Menu File -> Add/Remove Snap-in...
3. Select Certificates -> Add -> Computer account -> Local computer -> Finish
4. OK the Add or Remove Snap-ins dialog. The console should now contain Certificates (Local Computer).
5. Select Certificates (Local Computer) -> Trusted Root Certification Authorities -> Certificates.
6. Menu Action -> All Tasks -> Import....
7. Enter the path to the exported certificate, e.g. <computername>.cer.
8. Place all certificates in the following store -> Trusted Root Certification Authorities.
9. Finish. You should no longer receive the warning.

Move Certificate on Client

If you already installed the certificate through the warning dialog, you can find the certificate in the current user's store. Skip the steps above and just move the certificate to the right place:

1. Follow steps 1 to 3 as described in "Import Certificate on Client."
2. Add another Certificates snap-in, this time for My user account.
3. The certificate should be here somewhere. Try Certificates - Current User -> Intermediate Certification Authorities -> Certificates first.
4. Drag-and-drop or cut-and-paste the certificate to Certificates (Local Computer) -> Trusted Root Certification Authorities -> Certificates. Note that the certificate stores stack, so you will still see the certificate in you user's store! You should no longer receive the warning.

Unfortunantly, Windows Server 2008 has no support for themes over TS. As the Desktop Window Manager (DWM) is turned off when a TS connection is started. The client version / RDP settings does not matter.

You should login to that account locally (not though RDP) and disable any themes.