This can happen if the Sandbox option is enabled and you are using live API Credentials or Vice Versa.
It can also happen if you have not accepted the billing agreement with paypal.
sometimes, paypal just generates bad API credentials, if all else fails, generate new ones.