From my testing and with help and details from TheEndless, it appears my specific issue was with Apache2 servers running SSLv3 disabled and TLS1.0.
Using TLS1.2 for the SSLProtocol seems to solve the problem and requires at least Apache2 version 2.2.23.
If you're running Apache that should be helpful for your hosting provider.
Unfortunately I couldn't find the specific details on the 6.1 update.
