I went to your site and ran a test transaction to see at what point the failure was occurring. I experienced this failure when coming back to your site from PayPal. Here is the URL that was present:
checkout_failure.php?shipping=fail
This tells me that it is your shipping quote that is failing and not the checkout. You should do like you did for the checkout and put the full request and full response on this checkout failure page for your shipping provider. Please post back with this info after you run a test.