I stumbled upon this question and answer. I have the same problem as the OP, and am sorry to report that the proposed answer does not resolve it. Certificate in question has been verified by OpenSSL-1.0.2h:
$ openssl verify -verbose -CAfile Forest\ CA\ 2\ RSA.pem -purpose sslclient yubi-sign-test.pem yubi-sign-test.pem: OK
Here's its content:
X509v3 extensions: X509v3 Basic Constraints: critical CA:FALSE X509v3 Key Usage: critical Digital Signature, Non Repudiation X509v3 Subject Alternative Name: email:firstname.lastname@example.org X509v3 Subject Key Identifier: 75:35:D2:A3:47:A2:A1:20:AC:A3:90:DD:15:C2:A5:96:73:2B:75:9D X509v3 Extended Key Usage: TLS Web Client Authentication, Code Signing, 188.8.131.52.4.1.3184.108.40.206, 1.2.840.1135220.127.116.11, E-mail Protection, Microsoft Smartcardlogin Signature Algorithm: sha256WithRSAEncryption
Here's the content of the CA:
X509v3 extensions: X509v3 Basic Constraints: critical CA:TRUE, pathlen:4 X509v3 Subject Key Identifier: critical BD:1C:AE:9E:49:AE:68:B3:EC:7C:1E:AE:6A:CC:87:CB:F2:49:9E:A2 X509v3 Key Usage: critical Digital Signature, Non Repudiation, Certificate Sign, CRL Sign X509v3 Extended Key Usage: critical Time Stamping, OCSP Signing X509v3 Authority Key Identifier: keyid:BD:1C:AE:9E:49:AE:68:B3:EC:7C:1E:AE:6A:CC:87:CB:F2:49:9E:A2
Yet the current stable Firefox (47.0) is giving me that same message, and refuses to use that certificate for establishing a TLS session (doesn't even offer it among the available certs). It shows this certificate (among others) in Prefs->Advanced->View Certificates.
Needless to say, CA that issued this certificate, was imported to "Authorities" and marked as trusted for all the three options.
The only possible thing that I could think of - this CA does not offer CRL or OCSP, so neither it not the certs it issues have pointers to CRL or OCSP.
One suggestion I got was:
Welcome on Security SE. Do not hesitate to post your question as a new question referencing this one. Details of both the CA and end-user certificates can be helpful. However, before doing so you should try to add the "Key encipherment" key usage to the certificate as a first step. In case it does not help, try to add "Data encipherment" and remove "Non repudiation" (or disable the "Critical" flag on these extensions).
The problem with the above is that we have fairly strict rules on the Key Usage attributes, particularly on certificates that that are provisioned to hardware tokens. So it is not possible for us to, e.g., remove "Non-repudiation" from a Digital Signature cert, or add "Key Encipherment" to it. (Even in the unlikely case that the stupid current-release Firefox would work with such a cert, we wouldn't be able to deploy it.)
I'd appreciate any help.