"Could not generate DH key pair on the destination URL" error

What could cause a Could not generate DH key pair on the destination URL error?

A EDI partner company tries to connect to our HTTPS server and encounters the above message.

Or system uses a commercial firewall and reverse proxy (Apache based) with a high security ranking ('A' at qualsys ssltest). I suspect that our security level is higher than the capabilities of our EDI partner company, however they claim to have working connections with other HTTPS partners, and they say that they support '2048 bits'.

Unfortunately we can not lower the security level in our system for test purposes. Are there standard diagnostics tools which we can recommend our EDI partner so that they can analyze the connection failure?

Update: I used the Qualsys diagnostics tool for SSL and found that for Java (Sun JRE) 6 clients no connection is possible because

Java 6u45 - Client does not support DH parameters > 1024 bits.

For other A-rated servers however, Java 6 clients can connect, and it seems that they just do not use DH:

Java 6u45 - TLS 1.0 - TLS_RSA_WITH_AES_128_CBC_SHA (0x2f)

So if I put these pieces together, I assume that our server insists on DH key exchange (which is not supported for Java 6 clients), while other servers are able to negotiate a different cipher so that Java 6 clients can connect. However I am not an expert in this area, so please let me know if I am chasing a red herring :)