In the body of the checkout failure page add this:
<?php
var_dump($_SESSION);
?>
That will give you more information including the reason for failure.
Did you upgrade your paypal account to allow direct credit card transactions? That is usually the issue. You need to sign up for this and there is a monthly charge.