You're correct to guess that Fiddler does not have "fallback" logic
that is present in most browsers.
The most likely explanation is that the server is buggy and doesn't
perform a valid TLS handshake. Discussion of one variant of this
problem, including a workaround configuration change to Fiddler, can
be found here:
http://blogs.msdn.com/b/ieinternals/archive/2009/12/08/aes-is-not-a-valid-cipher-for-sslv3.aspx.
If switching to use just SSLv3 doesn't work, please let me know.
A low-level capture (e.g. Netmon) would allow me to see what exactly
is wrong with the handshake.