SSL handshake failure using client certificate and Retrofit

I have a client-server application (Android client, Apache Http server) communicating through mutual authentication (TLS 1.2). The problem: Sometimes the connection (login) fails with an SSL error.

This works:

1. Enrol client certificate
2. Login

This does not work:

1. Enrol client certificate
2. Login
3. Delete client certificate
4. Enrol ("same") client certificate
5. Login

Note: Killing the app after step 4 and then start it and perform step 5 works.

Possible explanations that I can think of:

1. Some old resources being reused (like the old client certificate). It looks like everything relevant (OkHttpClient etc) is re-instantiated as expected.
2. SSL renegotiation Perhaps this is broken when using a new credential? Is there a way to disable it?

Android (client) logs:

02-11 15:58:29.827  21352-23374/com.mycompany E/com.mycompany.Connection﹕ ERROR Read error: ssl=0x99116c00: Failure in SSL library, usually a protocol error
    error:1409441B:SSL routines:SSL3_READ_BYTES:tlsv1 alert decrypt error (external/openssl/ssl/s3_pkt.c:1303 0x9928fa60:0x00000003)
    error:140940E5:SSL routines:SSL3_READ_BYTES:ssl handshake failure (external/openssl/ssl/s3_pkt.c:1036 0xa613bcc5:0x00000000)
    retrofit.RetrofitError: Read error: ssl=0x99116c00: Failure in SSL library, usually a protocol error
    error:1409441B:SSL routines:SSL3_READ_BYTES:tlsv1 alert decrypt error (external/openssl/ssl/s3_pkt.c:1303 0x9928fa60:0x00000003)
    error:140940E5:SSL routines:SSL3_READ_BYTES:ssl handshake failure (external/openssl/ssl/s3_pkt.c:1036 0xa613bcc5:0x00000000)

Server logs:

[Thu Feb 11 14:58:16.736172 2016] [ssl:error] [pid 4424:tid 2088] [client 194.161.218.157:36836] AH02261: Re-negotiation handshake failed
[Thu Feb 11 14:58:16.736172 2016] [ssl:error] [pid 4424:tid 2088] SSL Library Error: error:0407006A:rsa routines:RSA_padding_check_PKCS1_type_1:block type is not 01
[Thu Feb 11 14:58:16.736172 2016] [ssl:error] [pid 4424:tid 2088] SSL Library Error: error:04067072:rsa routines:RSA_EAY_PUBLIC_DECRYPT:padding check failed
[Thu Feb 11 14:58:16.736172 2016] [ssl:error] [pid 4424:tid 2088] SSL Library Error: error:1408807B:SSL routines:ssl3_get_cert_verify:bad signature
[Thu Feb 11 14:59:24.655282 2016] [ssl:error] [pid 4424:tid 2088] [client 194.161.218.157:34530] AH02261: Re-negotiation handshake failed
[Thu Feb 11 14:59:24.655282 2016] [ssl:error] [pid 4424:tid 2088] SSL Library Error: error:04067084:rsa routines:RSA_EAY_PUBLIC_DECRYPT:data too large for modulus
[Thu Feb 11 14:59:24.655282 2016] [ssl:error] [pid 4424:tid 2088] SSL Library Error: error:1408807B:SSL routines:ssl3_get_cert_verify:bad signature

My setup:
Android version 5.1.1
Retrofit version 1.9.0
OkHttp version 2.7.2
Apache HTTP server version 2.4.17

Any clues what could be wrong or suggestions what to do to get to the bottom of this?

I bypassed the issue by not setting the ConnectionPool explicitly on the rest adapter (thus the same, default, instance is re-used).