Paypal Express Issue

Hey guys, I'm having a very frustrating problem integrating PayPal Express with my site. I have set up with PayPal Sandbox, and have double checked to make sure I am using sandbox credentials. Here's what happens...

The customer can click on checkout, then they enter their shipping info, then they are taken to PayPal and enter their credit card info, then they return to my website to make the final payment, this is when things get interesting...they click on the "Confirm Payment" button, and then I get the following messages:

-There was a problem connecting to PayPal. Please try again.
-There was a problem finalizing your purchase with PayPal. Please go back and try again.
-Whoops, looks like you skipped a step! Please go back and try again

I initially thought this was a problem with PayPal. However, I checked my Sandbox PayPal account for the test seller, and the 'payments' had come through, meaning PayPal has successfully charged the customer. I've tried disabling my other plugins, but they don't seem to have any effect on the outcome.

I wanted to know if I'm just doing something wrong with some setting or another. Thanks in advance!