Issue pending certificate, not apearing on client

You are following the right steps (http://support.microsoft.com/kb/316898/en-us), but the error likely means that you either have no enterprise certificate authority (CA) in the domain, or the CA is not accepting new certificate requests for some reason. It may also be that your installed CA is not allowing generation of "Computer" certificate types. This can be checked in the CA configuration.

The solution depends on whether you already have an enterprise CA set up and configured. If not then you need to create one (there is guidance on the Microsoft technet site, but it's not trivial) or else use another way of generating self-signed SSL certificates such as one of the free downloadable tools.

Well, I think I found the answer all on my own. When users attempt to encrypt a file or folder, their computer looks for a certificate to perform the encryption with. If they do not have a valid certificate to encrypt with, their computer looks for a CA that will issue them Basic EFS certificate. If no CA exists, then their computer will create its own self-signed Basic EFS certificate.

I'm paraphrasing Microsoft's explanation, which can be found here.