You might look carefully at the SSL certificate. There are number of things that need to be just right about it, and it is possible to build a certificate which is not up to snuff
Also there are different versions of some of the protocols involved and not all browsers support all of the versions ( e.g. older browsers...).
Also, a certificate will not be trusted if the browser cannot establish a chain of trust to the certificate. So take a look at what the certificate chain looks like. Start with the certificate itself, probably by going to where you got it from and asking there.
My certificate provider has a utility to show what the trust chain is to the root CA (certificate authority). Then also look at the certificates in the browser where it failed - is there a trust chain from there to the same root CA?
Not all well known CA signed SSL certificates are the same. The One free cert at StartSSL for example isn't verified as much:
"90.) Why are Class 1 certificates free? ... Since Class 1 certificates are domain and/or email validated only and the process is performed mostly by electronic and automatic means, StartCom doesn't apply any fees for this type of certification." (1)
And Stripe.com (mymy credit card processing company) says:
"You should buy an SSL certificate from a good certificate provider. We recommend DigiCert — their certificates have very wide acceptance (and in particular should work well on mobile browsers, where many other certificate providers fall short). NameCheap is another good option. They have slightly lower acceptance but their basic certificates cost $10 to $20." (2)
It is interesting to note this StartSSL's FAQ page is NOT served by https, while Stripe's help is.
So this is one example of how certificates could fail.