maggiesmom,

Can you go into your PayPal Express Checkout module settings and turn on Debug Log To File, and then make sure the log folder is set to read+write permissions:
/includes/modules/payment/paypal/logs

Then attempt an express-checkout transaction. When the "invalid data" error appears, go grab the log files via FTP, zip them up, and post the zip here for analysis.

The actual cause of the error should be shown in the logs.