Just ask and I can create an incident if and when necessary. But we are getting somewhere now. The issue is with the shipping settings.
Who are you using as your shipping provider? The next thing to do is to add debug information to the checkout_failure.php page so we can tell why it is failing.
Shipping information including errors is stored in the session. If you tell me your shipping provider I can walk you through adding that code to the page so you can see why it is failing.