Ssl – AD server not using cert for Active Directory LDAP + SSL

I'm trying to enable SSL for Active Directory in our domain. The problem I'm running into is that the server is failing to recognize the certificate I've made for it. Whenever I try to query the server using ssl (using ldp.exe), I get event 36886 which basically states that a suitable certificate could not be found on the server.

I've gone through this kb article for troubleshooting and here's what I've got

• I've placed the cert on the local machine's certificate store, under the Personal container. I used openssl on a Linux machine as the CA and have placed its certificate under the Trusted Root Certification Authorities container.

• My domain controllers FQDN is in the Subject of the cert. An alternate name has also been added in the extendedKeyUsage section, neither works when querying.

• I have serverAuth and clientAuth in the EnhancedKeyUsage section

• When I double click the cert in the mmc console, it states at the bottom that "You have a private key that corresponds to this certificate" however, as per the KB instructions I run thecertutil -verifykeys command and it returns The system cannot find the file specified.

• When I double click the cert and go to Certification Path, it lists my CA and then the certificate, then below it says This certificate is OK, so I'm assuming that means the chain is valid.

• It's the only certificate in the Personal store for the computer

• When I do something like certutil -verifystore MY 0 it lists the cert and the only complaints it has is about the revocation list because I never made a crl, but it still says the certificate is valid at the end.

I'm guessing the reason it's failing is tied to why certutil -verifykeys is failing, but I haven't been able to find what it actually means when I get the error that I do.

Can anyone point me in the right direction?