If the only message in the popup under the "Certificate errors" header is "The certificate is not from a trusted certifying authority", then the only problem with the certificate is that neither it nor the certificate from the issuing CA is found in the RDP applet's trust store yet. Check the "Do not ask me again for remote connections to the computer" checkbox in the popup before clicking on the OK button. This will add the certificate chain to the trust store, and the popup will not come up the next time the user connects to this target device via the RDP access method. There should be no warnings about an untrusted certifying authority for first-time connections to other devices with certificates issued by the same CA, once the CA certificate is in the store.
PAM Engineering is working on an enhancement that will allow PAM users to launch native RDP clients like mstsc. This may be available in the next release, planned as PAM 3.3 at the time of this writing. With this enhancement the native client would be expected to do the certificate checking.