Handshake failure although the root certificate is installed (PayPal upgrades - g5 certificate - openssl)

I have (and cannot upgrade for several reasons) several virtual machines running Centos 5.11

As a check to verify the machines are compatible with new PayPal updates described here: https://www.paypal-knowledge.com/infocenter/index?page=content&widgetview=true&id=FAQ1766&viewlocale=en_US

I ran this in a shell:

grep -C 5  --color=always "VeriSign Class 3 Public Primary Certification Authority - G5" /etc/pki/tls/certs/ca-bundle.crt

Everything looked fine, this is the output:

Data: Version: 3 (0x2) Serial Number: 18:da:d1:9e:26:7d:e8:bb:4a:21:58:cd:cc:6b:3b:4a Signature Algorithm: sha1WithRSAEncryption Issuer: C=US, O=VeriSign, Inc., OU=VeriSign Trust Network, OU=(c) 2006 VeriSign, Inc. - For authorized use only, CN=VeriSign Class 3 Public Primary Certification Authority - G5 Validity Not Before: Nov 8 00:00:00 2006 GMT Not After : Jul 16 23:59:59 2036 GMT Subject: C=US, O=VeriSign, Inc., OU=VeriSign Trust Network, OU=(c) 2006 VeriSign, Inc. - For authorized use only, CN=VeriSign Class 3 Public Primary Certification Authority - G5 Subject Public Key Info: Public Key Algorithm: rsaEncryption Public-Key: (2048 bit) Modulus: 00:af:24:08:08:29:7a:35:9e:60:0c:aa:e7:4b:3b:

To me, this means that the new required G5 root certificate is actually in there. However, when testing against the sandbox which should already be using the new specs with this command:

openssl s_client -connect api-3t.sandbox.paypal.com:443 -showcerts

The response is:

CONNECTED(00000003)
2052:error:14077410:SSL routines:SSL23_GET_SERVER_HELLO:sslv3 alert handshake failure:s23_clnt.c:586:

Of course, no issues when doing the same on the non-sandbox link.

I am 101% stuck here. The cert is there, but I still get a failure? Installed Openssl (and latest avail through official repos) is openssl-0.9.8e-40.el5_11.

I saw several other questions about the handshake issue, but none of them seem to address an issue like this (certificate in place but still issues connecting).

Any idea about why this is happening?

EDIT: by also trying to folrce ssl3 in the call this way:

openssl s_client -ssl3 -connect api-3t.sandbox.paypal.com:443 -showcerts

I get this instead:

CONNECTED(00000003)
6064:error:14094410:SSL routines:SSL3_READ_BYTES:sslv3 alert handshake failure:s3_pkt.c:1092:SSL alert number 40
6064:error:1409E0E5:SSL routines:SSL3_WRITE_BYTES:ssl handshake failure:s3_pkt.c:536: