on the checkout_failure.php page add the following code to write the session contents to the page:
<?php @session_start(); var_dump($_SESSION); ?>
this will include the response from the shipping provider with details on why the shipping lookup failed.