Add this code to the body of the checkout failure page:
<?php
var_dump($_SESSION);
?>
That will show you more information about the error including an error description and code that could shed light on why it isn't working. View source for better readability.
If you can't figure it out from there, post the returned code (from the source view) into the private area (since it will include your credentials) and I can try to see if I can spot the problem.