in the power store admin section, goto Settings -> Store Settings and enable the Debug Mode Setting.
this will write the session data to the checkout failure page and include the full request sent to paypal and the full response from paypal, the full response will help determine the cause of the failure.
NOTE: Post the full debug info in a private message.