More then likely, you have PayPal (PayPal.com in the back of the cart, sometimes called "PayPal Traditional") set to use HTTPS.
When passing data over to Paypal, the correct protocol is HTTP. This is managed through the payment gateway area in the adminstrator area of the cart. If you see Paypal is set to HTTPS, change it to HTTP.
If you are using Paypal Pro, you will need to use the HTTPS (secure) protocol and have a security certificate attached to the cart.
