When attempting to connect to an xmpp server over SSL, openssl fails with the following error: 3071833836:error:140790E5:SSL routines:SSL23_WRITE:ssl handshake failure:s23_lib.c:177

I believe that the server uses the RC4-MD5 cipher, here is the full output:

[root@localhost ~]# openssl s_client -connect 184.106.52.124:5222 -cipher RC4-MD5
CONNECTED(00000003)
>>> SSL 2.0 [length 0032], CLIENT-HELLO
    01 03 03 00 09 00 00 00 20 00 00 04 01 00 80 00
    00 ff b0 c9 c2 3f 0b 0e 98 df b4 dc fe b7 e8 8f
    17 9a 34 b5 9b 17 1b 2b ac 01 dc bd 2b a9 2d 18
    44 0c
3071866604:error:140790E5:SSL routines:SSL23_WRITE:ssl handshake failure:s23_lib.c:177:
---
no peer certificate available
---
No client certificate CA names sent
---
SSL handshake has read 0 bytes and written 52 bytes
---
New, (NONE), Cipher is (NONE)
Secure Renegotiation IS NOT supported
Compression: NONE
Expansion: NONE
---

Using gnutls-cli:

[root@localhost ~]# gnutls-cli 184.106.52.124 -p 5222
Resolving '184.106.52.124'...
Connecting to '184.106.52.124:5222'...
*** Fatal error: A TLS packet with unexpected length was received.
*** Handshake has failed
GNUTLS ERROR: A TLS packet with unexpected length was received.

Connecting to the same server on port 5223 works fine.

Using OpenSSL 1.0.1e-fips on CentOS 6.5 and OpenSSL 1.0.1f on Ubuntu 14.04.1

Any tips on how to troubleshoot this? Thanks in advance.