Remote desktop connection problem

[ABCDEFG]

I get an error about not having a valid Certificate Authority when I try to connect remotely to another computer (that's not part of my LAN network).

 

What are some possible reasons for this problem and some possible solutions to the possible problems?

[Cap'n Refsmmat]

Are you using an encrypted (SSL or TLS) connection to that computer? If so, the certificate that computer is using is not certified by a Certificate Authority. That will not compromise the security of the system in any way -- it only means the person on the other end has not paid several hundred dollars to have a company check to make sure they are who they claim they are.