We are lucky guys, I've resolved the issue, here is how, it seems PayPal became more strict about addresses,
and what happens in Prestashop is this, it does not send the country code, hence people from Canada, Australia, etc having issues,
to fix that if you are using PayPalUSA plugin, it does 2 wrong things sends "address2" variable as "undefined" and does NOT send the country code.
So here is the fix:
Go to /modules/paypalusa/views/templates/hooks/standard.tpl (if you are using standard paypal gateway, if you are using different one you have to edit
payment-advanced.tpl or express-checkout.tpl)
and edit these lines:
line 28-29:
{if ($paypal_usa_billing_address->address2 != '')}<input type="hidden" name="address2" value="{$paypal_usa_billing_address->address2|escape:'htmlall':'UTF-8'}" />{/if}
to this:
{if ($paypal_usa_billing_address->address2 != '')}{/if}<input type="hidden" name="address2" value="{$paypal_usa_billing_address->address2|escape:'htmlall':'UTF-8'}" />
this way the address2 will be in the paypal inputs even if it's empty, so you won't get "undefined"
then also add this line for country iso_code to send to paypal, right after address2 line or after state, as you wish:
<input type="hidden" name="country" value="{$paypal_usa_billing_address->country->iso_code|escape:'htmlall':'UTF-8'}" />
This will add the country parameters that will be sent to paypal, this way paypal will recognize the address and issue will be resolved.
This has fixed the issue for me, hope it fixes it for you!