Client Side certificate authentication failure
Solution 1:
The same way that server certificates uniquely identify a server (or domain), client certificates uniquely identify a client. And just like server certificates must be signed by someone the client trusts, client certificates must be signed by someone the server trusts.
Usually, when you configure a server to accept client certificates, you specify a signing certificate that must be used to sign the client's cert. This lets the server know that the client is "authorized", whatever that might mean in your context, since presumably you'll only sign certificates for "authorized" users.
Allowing client certificates without doing any sort of verification is generally possible with most servers, but sort of defeats the whole purpose.
Solution 2:
It depends on the type of server certificate. Sometimes self-signed certs can be problematic. If it is signed by a Certificate Authority, generally the client certificate will also have to be signed by the same CA and may need the entire certificate chain included as well.
You can use openssl to gather some information on acceptable CAs for client certificates with the command line:
openssl s_client -connect host.domain.tld:443
or whatever port SSL is listening on. This should give information about the certificate chain all the way up to the root CA and also provide acceptable CAs for client certificates as well.