On your checkout failure page you need to add in the bindings that will tell us what the specific issue is with the shipping. Put this code into the page where you would like to see the data for the shipping:
<?php echo $_SESSION["WA_Store_Cart_UPS_FullRequest"]; ?>
<?php echo $_SESSION["WA_Store_Cart_UPS_FullResponse"]; ?>
Please test this out and post back with whatever you discover.