PayPal Express Checkout Error

I am getting the following error every time I try to checkout from my site This is a supporter site using MarketPress with PayPal Express Checkout

“There was a problem connecting to PayPal to setup your purchase. Please try again.

10736 – Shipping Address Invalid City State Postal Code – A match of the Shipping Address City, State, and Postal Code failed.”

I have tried using sandbox credentials and regular ones with no luck. Obviously I have tried changing addresses also. Any thoughts on this?

ps. I have also disabled all plugins and only left the Supporter and MarketPress mu-plugins enabled