How do I reissue machine certificates for my Active Directory members now that I have a private CA?

So I have a working Active Directory. I've recently added a new machine to act as an Active Directory Certificate Authority.

I've added a Group Policy (Computer level) for automatic certificate enrollment according to this document. And verified that my CA appears in all of my domain members' Trusted Root Certificates.

I've exported the CA's root certificate and added it to my workstation's (computer) Trusted Root CA list.

When I want to remote desktop into my remote servers, it still pops up a warning like this:

When I view the certificate, it's clear that the certificate that is being sent is the default machine self-signed certificate. How do I get Windows to re-issue machine certificates based on my new trusted root CA? I'm guessing that I need to create an auto-approval policy for machine certificates somewhere with some constraint maybe on who/how such requests can be made. And then I would guess that I need to push a domain policy that somehow instructs all my domain members to get their machine certificate.

Does this sound familiar to anyone? I think the reason I can't find a document on this is because I don't know the correct terminology.

Solution 1:

You need to enroll for a machine certificate on the workstation. You can setup autoenrollment via group policy or you can navigate to the cert enrollment website on your CA (https://yourCA/certenroll and enroll manually.
Autoenrollment is set under Computer Config -> Policies -> Windows Settings -> Security Settings -> Public Key Policies.

EDIT After getting a certificate that can be used for "Client Authentication" you need to setup RDP to use the cert. Follow instructions here for a WMI script to do this.

Solution 2:

This microsoft documentation might help you: http://support.microsoft.com/kb/281271

"In the following scenarios, if a user from the same domain as a certification authority (CA) requests a certificate, the issued certificate is published in Active Directory. However, if the user is from a child domain, this process is not successful. Also, when users from the same domain as a CA request a certificate, the issued certificate may not be published in Active Directory. "