Let me start by saying there are many reasons this can happen, it's best to start with a good and known to work template.
Here are some common things that cause this message:
Here is what happened to my client and may be happening to others:
Mixing up your public key and PayPal's public key, it sounds funny but I've seen this enough times.
So make sure you check the contents of all the keys, see if they match. It's easy when transferring the keys around to different machines to mix them up.
Solution was to make sure your public key and paypal's public key don't get mixed up. I saw a case where both keys were the same (either both were PayPal or both were the client's public key).