Add this code to your checkout failure page:
<?php
var_dump($_SESSION);
?>
Then go through it again. That will have the communications with the payment provider as well as any error messages which we can use to identify the problem.
If you need help diagnosing it, just view the source code and send me the result and I can help you pick out the error.