This error is happening in my installation too. I was thinking that it might be a problem in the way my php has been configured or else in the SSL communication (probably does not work fine in combining my private key and certificate with the paypal RSA and Certificate). Do I need to have a CERTIFICATE and PRIVKEY that reflect the information that i got in the sandbox profile??? For instance in my certificate i have just the Common Name specified.
Moreover, I have noticed that this problem does not happen when I disable encryption.
Hope you got an answer to my prob,