I am using MMC with the certificate management snapin. I am requesting certificates from a brand new installation of a CA.
Requesting User certificates works perfectly. Requesting Computer certificates fails and says the RPC service is unavailable.
What should I check?
Personally, I'd take a network trace to see how far you get. Sounds like a permissions issue bubbling up as RPC error.
http://blogs.technet.com/b/askds/archive/2007/11/06/how-to-troubleshoot-certificate-enrollment-in-the-mmc-certificate-snap-in.aspx might help give troubleshooting guidance.
Try testing connectivity and permissions by running:
on the computer requesting the certificate. The FQDN is the fully qualified name of the certificate authority and CAName is the subject name of the certificate for that CA.
Cert Requests can use DCOM/RPC and it sounds like this may be your issue. Additional info and troubleshooting steps can be found at https://techcommunity.microsoft.com/t5/ask-the-directory-services-team/how-to-troubleshoot-certificate-enrollment-in-the-mmc/ba-p/394973.