I have same problem, in my case i checked if i modify country ISO code it worked OK Argentina for example, if i write iso code "AR" don't work for paypal, but if i write "CO" (iso code of Colombia) it work fine, some iso codes work fine, but some others not. My Prestashop Version is 1.3.1.1 , in old version v.1.1.0.5 worked fine. I don't sell products, i sell service.