こちらの記事で書きましたが、PayPalへの通信がTLS V1.2に強制移行されます。（2016年6月予定）
すでにSandboxは移行されており、通信のテストができますが（テストの詳細はこちらを参照してください）、PHPのcurlを使った通信実装で問題が起きるケースがあるようです。
実際に通信エラーになった時の対応方法を参考までに載せておきます。（もちろん、環境や実装方法により対応は異なるのであくまで一例です）
Curlの接続オプションに明示的にTLSオプションを指定
curl_setopt($conn, CURLOPT_SSLVERSION, CURL_SSLVERSION_TLSv1);
（$connはHTTP接続のコネクションインスタンス）
PHPのバージョンによってCURL_SSLVERSION_TLSv1が定義されていない場合は
curl_setopt($ch, CURLOPT_SSLVERSION, 1);
とする。
これだけで解消する場合あり。
（上記で解消しない場合は）サーバーの関連するライブラリのバージョンを上げる
上記で解決しない場合、あるCentos 6サーバーでは以下のライブラリを古いものから以下のバージョンに引き上げたところ解消しました。
openssl 1.0.1e-42.el6_7.4
curl 7.19.7-46.el6
nss 3.18.0-5.3.el6_6（curlと依存関係になるので必然的に上がります）
詳しいライブラリやバージョンの情報、脆弱性そのものを説明は、HeartBleedの説明やその対応のページを参照することをお勧めいたしますが、opensslの場合は、以下のように、バージョンを上げずに、tls1オプションで回避できることもあるようです。
https://teratail.com/questions/9776
PHP編と銘打ったので、本当は他の言語版も載せたいのですが、なかなか事例収集が難しいので、もしご協力いただける方がいたら幸いです。
なお、上記の対応は、PayPalユーザーでなくても今後必要となってくる対応ですので、早めのセキュリティ環境の整備をお勧めします。