The *feeling* that the problem is related to SNI is getting stronger.

This is the error log when running ssllabs.com on the server:

==> stderr.log <==
2015/03/17 17:12:45 [crit] 40733#0: *925 SSL_do_handshake() failed (SSL: error:14094085:SSL routines:SSL3_READ_BYTES:ccs received early) while SSL handshaking, client: 64.41.200.104, server: 0.0.0.0:443
2015/03/17 17:12:46 [crit] 40733#0: *926 SSL_do_handshake() failed (SSL: error:14094085:SSL routines:SSL3_READ_BYTES:ccs received early) while SSL handshaking, client: 64.41.200.104, server: 0.0.0.0:443

It corresponds to the handshake simulation, and in particular to the failed handshakes
with all non-SNI browsers, emphasis on "all". The SNI clients that fail are java7u25 and openssl 0.9.8y.
All other clients succeed.