To determine what might be going wrong with your PayPal checkout you will need to have the full request and full response on your checkout failure and pp_checkout failure pages. Here is a link that provides the specific code that you need to add to these pages:
showpost.php?p=34342&postcount=3
Please give this a try and let us know what the response message says, it should let you know just why it is failing.