It could be a few things:
1) In the address bar, is there a shipping=failed querystring? This would mean a shipping rate error. What shipping provider are you using?
2) If the PayPal API Information is not correct, the paypal server may refuse the connection and send you to the failure page without a response.
double check the paypal information is entered correctly.