I've worked over a hundred of these, and I may yet get around to posting my findings and methods.
That error message can occur for any number of reasons. Sometimes a packet trace on the server side will show that the server ended the handshake with an error, and sometimes it will just drop the connection (FIN).
And, servers now will do it for the snobbiest of reasons, like allowing SSLv3 in the client hello. It doesn't matter if you have TLS 1.2 enabled. It's as if you might have contracted an infection, it just slams the door in your face. But can also be that your settings are too strict.
Technically, the answer is likely in the server hello, but the Qualys server test is a lot nicer for this work.
Scroll down to the cipher list. You've like got some marked in red and orange. What I've been seeing lately is one orange (weak) one that requires 3DES and SHA1--and nothing better.
Here's a nice cipher suite for those: HIGH:SSLv3:!SEED:!IDEA:!aNULL:!eNULL:!ADH:!CAMELLIA:!PSK:!RC4:!MD5:-ECDH:ECDHE: -DH:-kEDH:DHE:@STRENGTH:+RSA
(A slightly stronger intermediate cipher suite [by today's standards] that disables 3DES and SHA1: HIGH:!aNULL:!eNULL:!3DES:!ADH:!CAMELLIA:!PSK:!RC4:-ECDH:ECDHE:-DH:-kEDH:DHE:-SE ED:+RSA:@STRENGTH)
The thing about SHA1 is that McAfee decided it would be helpful to have a check box for it: "Allow legacy signatures in the handshake [If check, SHA1 signatures will be allowed.]"
These are the most likely issues, but there are plenty of others.
There are many that can't do RFC 5746, but there's a separate error messages for that which says "unsafe legacy..." (I forget the rest).
And, there are only a handful that can't take a plain text fragment. You only get to discover this one by hacking though.
If you want to tighten up you TLS settings, you're going to end up with a white list or seven for sites that are behind the times. Yes, you can have multiple certificate verification settings
I'll compile a list of the cipher suites I've created.
I've been accused of going overboard with these settings, but I wouldn't have learned what I now know if I hadn't.
I'm now have five different cipher suites in use, and a destination has to be on a white list to use the weaker ones (after scrutinizing the destination for safety).
Settings Name Cipher Suite Cert. Verification, Highest-Strength, TLS HIGH:-ECDH:ECDHE:!aNULL:!eNULL:!3DES:!kEDH:!ADH:!CAMELLIA:!DH:!PSK:!AES128:!RC4: @STRENGTH:+RSA Cert. Verification, High-Strength+DHE+AES128 HIGH:!aNULL:!eNULL:!3DES:!ADH:!CAMELLIA:!PSK:!RC4:-ECDH:ECDHE:-DH:-kEDH:DHE:-SEE D:-SHA1:+RSA:@STRENGTH Cert. Verification, High-Strength+DHE+AES128, SHA1 HIGH:!aNULL:!eNULL:!3DES:!ADH:!CAMELLIA:!PSK:!RC4:-ECDH:ECDHE:-DH:-kEDH:DHE:-SEE D:+RSA:@STRENGTH Cert. Verification, High-Strength+DHE+AES128, SHA1+3DES HIGH:SSLv3:!SEED:!IDEA:!aNULL:!eNULL:!ADH:!CAMELLIA:!PSK:!RC4:!MD5:-ECDH:ECDHE:- DH:-kEDH:DHE:@STRENGTH:+RSA Cert. Verification, Medium and High-Strength Ciphers HIGH:!aNULL:!eNULL:!3DES:!kEDH:!ADH:@STRENGTH
I actually have about nine settings in use, but they have either the RFC 5746 option checked or the Non-empty plain text fragment unchecked. I found that I needed a terse naming convention, and the settings with those two options variations are named as above with either "-5746" or "nePTF" appended (respectively).
Note that it was the Qualys SSL Labs server test that shows what the latest browsers are using, and I used that as a basis of which direction to go on the cipher lists (mentioned in another discussion).
I tested that address using the default SSL Cert. Verificatons settings, with Send empty plaintext fragment enabled, and legacy and handshake renegotiation without RFC 5746 disabled and it seems to negotiate fine.
As John mentioned, it's usually an issue with no matching ciphers, which I talked a bit about here: SSL Setting: Allow Legacy signatures in the Handshake After that it's usually the renegotiation issue.
What version are you currently running?