I've already created a bug report for that:
http://forge.prestashop.com/browse/PNM-3410
Copy/paste from the report:
Paypal ExpressCheckout API requires some addresses to include state (link to info at the end). If for some reason such state was not defined in a user's address, Paypal module finishes the payment flow with a "Fatal error" screen with no chance to recover. By default most of those (but not ALL) countries in a new Prestashop 1.6.0.14 installation require state. But this is not true when updating from old installation. I was updating from 1.4 and this is how I experienced the bug.
Steps to reproduce:
1. Clean Prestashop 1.6.0.14 install
2. Install Paypal module
3. Create an user with an address in Brazil (by default Brazil doesn't have states, but they are required in Paypal)
4. Buy with Paypal
5. Paypal doesn't complain about the wrong address - just ignores it
6. When You complete the steps in Paypal.com and you are taken to your store, Paypal doesn't return correct(any) address (as it was ignored). This results in a "Fatal Error".
When debug mode is enabled you can see some kind of debug info.
The most reviewing is this:
Notice: Undefined index: PAYMENTREQUEST_0_SHIPTOCOUNTRYCODE in .../modules/paypal/express_checkout/payment.php on line 91
I'm attaching the file.
List of addresses requiring states:
Argentina, Brazil, Canada, China, Indonesia, India, Japan, Mexico, Thailand or USA. Source: https://developer.paypal.com/docs/classic/api/merchant/SetExpressCheckout_API_Operation_NVP/#id09BHCD0707U__id107SHG090HS