The 4 basic principles of PKI Troubleshooting

First of all; PKI is easy once you understand the basic principles.  Don't give up :)

When troubleshooting PKI, the key point to understand what operation each of the parties involved does in order to determine where the point of failure is.

Most PKI cases I've handled over the years boil down to one of four things:

  1. Lack of trust - one of the parties involved doesn't trust the issuer of the other certificate.
  2. Lack of validity verification - one of the parties involved can't verify the revocation status of the other certificate or else it's simply expired or not yet valid.
  3. Incorrect purpose - the certificate being used isn't for the intended purpose (doesn't have the right OID) or else has an unsuitable keysize for the private or public key (too big or too small).
  4. Incorrect algorithm - one of the parties involved doesn't recognize the algorithm being used or is handling it differently than the other party.

A simple rule of thumb is that servers verify client certificates - clients verify server certificates.  It's therefore vital to look at the certificates from the POV of the entity doing the verification.
I.e. export the certificate and do checks on it on the other side of the conversation.  Verifying the server certificate should be done from the client, verifying the client certificate should be done from the server.

For example: Certutil -v -verify -urlfetch <exportedcert.cer> to check on the revocation status of an exported certificate.

Further reading:

Troubleshooting PKI problems on Windows
http://social.technet.microsoft.com/wiki/contents/articles/troubleshooting-pki-problems-on-windows.aspx

Appendix C: Certificate Revocation References
http://technet.microsoft.com/en-us/library/ee619758(WS.10).aspx