Java not sending client certificate

Question

I'm using HttpClient 4.2.3 on Java 1.7 to connect to a remote server hosted by nginx. My organization uses PKI extensively, and both the remote and the client have certificates issued by a common CA.

The server has a signing chain like the following:

CN=Server 123, OU=Servers, OU=My Division, O=My Org, C=US
CN=My Division CA, OU=My Division, O=My Org, C=US
CN=My Org CA, O=My Org, C=US

And the client has a signing chain like the following:

CN=Client 456, OU=Servers, OU=My Division, O=My Org, C=US
CN=My Division CA, OU=My Division, O=My Org, C=US
CN=My Org CA, O=My Org, C=US

For some reason, the client does not present its certificate to the server. The server is configured properly (curl with --cert, --key, and --cacert works, for example). The client has its cert, private key, and signing chain in the key store, and the "My Division CA" and "My Org CA" certs (among others) in its trust store. With SSL debugging on, I can see the key store and trust store load successfully. The client can connect to other servers that request certificates correctly. However, when trying to connect to "Server 123", I see something like the following:

*** ServerHello, TLSv1
...
** TLS_RSA_WITH_AES_256_CBC_SHA
...
*** Certificate chain
...
***
Found trusted certificate:
...
*** CertificateRequest
Cert Types: RSA, DSS
Cert Authorities:
<CN=My Division CA, OU=My Division, O=My Org, C=US>
<CN=My Org CA, O=My Org, C=US>
<CN=Some Other CA, OU=Some Division, O=My Org, C=US>
...
*** ServerHelloDone
...
*** Certificate chain
***
*** ClientKeyExchange, RSA PreMasterSecret, TLSv1
...
HTTP/1.1 400 Bad Request
...
No required SSL certificate was sent
...

The most confusing part is that other clients with the same software present their certificate and can connect just fine.

I have configured all of the infrastructure correctly (to my knowledge), and this should work. I really do not want to write and maintain custom SSL code to fix this.