Here a couple of points you may want to double check:
- Make sure your account is Premier/Business Verified (also email address confirmed),
- Correct Endpoint for the environment in use Sandbox/Live,
- Correct API Credentials for the environment in use Sandbox/Live,
- Correct APP-ID
If the issue still persists, I'd recommend to open a ticket at www.paypal.com/mts specifying the API response (with "correlationId" included)