Add this to the top of the checkout failure page:
<?php
@session_start();
var_dump($_SESSION);
die();
?>
Then send me the result after using view source so it is better formatted. I should be able to spot the error there and let you know what needs to be done.