Intermittent "sslv3 alert handshake failure" under Python

I have a REST API written in Java running under JBoss. Recently we updated our JVM from 1.6 to 1.7. This started to cause issues with only our Python clients which were connecting. Intermittently, Python clients are getting handshake failures. We wrote a very simple test which reproduces the problem:

import httplib2

for i in range(1,500):
    print i
    response, content = httplib2.Http(disable_ssl_certificate_validation=True).request('https://server.com:8443',)

Give the following output:

.
.
.
64
65
66
67
Traceback (most recent call last):
  File "api_test/test.py", line 6, in <module>
    response, content = httplib2.Http(disable_ssl_certificate_validation=True).request('https://server.com:8443/rest/solidtumor/2012/id/50d3216c092c8554b8b9f384?glossary=true&api_key=APIKEY',)
  File "/home/hostovic/api_test/httplib2/__init__.py", line 1445, in request
    (response, content) = self._request(conn, authority, uri, request_uri, method, body, headers, redirections, cachekey)
  File "/home/hostovic/api_test/httplib2/__init__.py", line 1197, in _request
    (response, content) = self._conn_request(conn, request_uri, method, body, headers)
  File "/home/hostovic/api_test/httplib2/__init__.py", line 1133, in _conn_request
    conn.connect()
  File "/home/hostovic/api_test/httplib2/__init__.py", line 914, in connect
    raise SSLHandshakeError(e)
httplib2.SSLHandshakeError: [Errno 1] _ssl.c:490: error:14094410:SSL routines:SSL3_READ_BYTES:sslv3 alert handshake failure

The 67th call failed on this run through, but it fails at different times each time the test is run.

Our other clients (Java, Groovy and Ruby) work without any problem.

If I switch the JVM back to 1.6 the failures stop.

I did an openssl check using:

openssl s_client -connect server.com:8443

and it returned this:

New, TLSv1/SSLv3, Cipher is EDH-RSA-D