Are you seeing the same issue on Windows platforms as well? Do you see any errors in the User Access Logs on the SA?
I hope you have already imported the cert into the Trusted Client CA list on the SA as well.
The easiest way to test is install the certificate in firefox or internet explorer and try to authenticate to the SA using the browser. If the certificate does not appear in the browser, then the certificate was issued incorrectly. In most cases, you'll want to make sure the key usage of 'client authentication' is enabled on the end user certificate.