I have followed the instructions to delete the G2 certificate and add the G5 one given on the PayPal website and I am still getting the SSL23_GET_SERVER_HELLO:sslv3 alert handshake failure.
The following code demonstrates the problem:
$ch = curl_init('https://api-3t.sandbox.paypal.com/nvp?'.$data);
curl_setopt($ch, CURLOPT_VERBOSE, 1);
curl_setopt($ch, CURLOPT_CAINFO, '/usr/local/etc/openssl/cert.pem');
curl_setopt($ch, CURLOPT_SSL_VERIFYPEER, true);
$response = curl_exec($ch);
Naturally, the problem is also evident when using the Omnipay Paypal Express gateway.