Tomcat client certificate authentication, client certificate not sent

I've add client certificate based authentication on our Tomcat servers. Both client and server are tomcat servers with internal CA issued certificates.

Each tomcat has its own keystore (PKCS12) containing its private key and certificate and a truststore (JKS) containing the CA public certifiacte.

After stating the Tomcat server for the first time, the authentication fails (results in 403). Upon restarting the tomcat, the authentication is successful. I've enabled debugging on the SSL and I've noticed that when the authentication fails, the client does not send its certificate but after restarting it does.

No errors appear in the log files.

Failed authentication log:

*** CertificateRequest
Cert Types: RSA, DSS, ECDSA
Cert Authorities:
<EMAILADDRESS=x@x.com, CN=x.x.x, OU=x, O=x., L=x, ST=x, C=x>
*** ServerHelloDone
*** Certificate chain
***
*** Found trusted certificate:

Succesful authentication log:

*** CertificateRequest
Cert Types: RSA, DSS, ECDSA
Cert Authorities:
<EMAILADDRESS=x@x.com, CN=x.x.x, OU=x, O=x., L=x, ST=x, C=x>
*** ServerHelloDone
matching alias: tomcat
*** Certificate chain
chain [0] = [

Any idea of what's causing it to work on the second try? Nothing changes on the tomcat servers...

Thanks