PayPal Express - 10002 security header is not valid error

This is what worked for me, stange but it did the trick Magento 1.8.1 Paypal Website

First, I went into Paypal.com account and enabled all API Access

1. Goto Profile > Request API credentials > Set up PayPal API credentials and permissions > Add or edit API permissions

2. Add New Third Party, or Edit Existing Third Party the username used for Magento

3. I granted all permissions, probably not necessary, but I figured it couldn't hurt

Then in Magento Admin:

1. Go to System > Configuration > PayPal > API/Integration Settings

2. Remove all values from API Username, API Password and API Signature from.

3. Go to System > Cache Management and clear all caches.

4. Put the API Credentials back in

 PayPal gateway has rejected request. Invalid token (#10410: Invalid token)

Enable Express Checkout (PayPal Navigation has changed to)

  Profile & Settings >> My selling tools >> API access >> Update
  Enable Express Checkout 
  Accept >> Submit.

Check Magento Paypal setting

 System >> Configuration >> Sales >> Payment Methods

Choose your PayPal option

Configue >> Set API Credential    

Enable paypal

 Enable this solution: Yes

Disable SSL if you do not have SSL

 Enable SSL verification : No

With Development Mode

 Sandbox Mode : Yes

Clear Magento Cache, Should work.

First, about error codes: https://developer.paypal.com/docs/classic/api/errorcodes/.

Second, if you haven't already, check this post: Required modifications for using Varnish on Magento CE. Maybe Varnish has cached your requests to PayPal.

Also check these articles: http://www.carlosrobles.com/blog/2010/10/magento-paypal-sandbox-paypal-gateway-has-rejected-request-security-header-is-not-valid-10002-security-error/ (this one is in Spanish, but it is understandable)

http://www.magentocommerce.com/boards/v/viewthread/205638/#t367616 http://www.exquisitelymixed.com/ecommerce/magento/paypal-gateway-has-rejected-request-security-header-is-not-valid-10002-security-error-in-magento/