It is probably an error in the shipping. The transaction will fail if the shipping fails. Perhaps a problem with the shipping api credentials.
To debug create a new blank page with just this code on it:
<?php
@session_start();
var_dump($_SESSION);
?>
Then go through the process until you see the failure page. Once you see the failure, manually browse to the url of the new page you created and it will have debug information that will help you identify the source of the failure.
If you have trouble deciphering it, you can post that result back here and I can comment. (view source on the page before copying and pasting it here because it will be easier for me to read, also make sure to post it to the private section because it could contain confidential API credentials)