add the following code to the failure page to return the full request and full response from usps:
<?php
@session_start();
echo "Full Request: ".(isset($_SESSION["cartName_UPS_FullRequest"])?htmlentities($_SESSION["cartName_UPS_FullRequest"]):"n/a")."<br />";
echo "Full Response: ".(isset($_SESSION["cartName_UPS_FullResponse"])?htmlentities($_SESSION["cartName_UPS_FullResponse"]):"n/a")."<br /></p>";
?>
where "cartName" is the name of your eCart object. Post the results of this back so I can see what is causing the problem.