If you add code to the checkout failure page:
<?php
var_dump($_SESSION);
?>
That will write information to the page that includes the reason why it failed. That is probably the best place to start in order to find and fix whatever is causing the issue.