when you get to the checkout_failure page, is there a query string variable in the URL like:
checkout_failure.php?shipping=false
it may be that shipping rate lookup is failing and causing the redirect to the checkout failure page.
try adding the following to the failure page for troubleshooting:
<?php
if(!session_id()) session_start();
echo "eWay Full Request: ".(isset($_SESSION["eWAY_XML_postedValuest"])?htmlentities($_SESSION["eWAY_XML_postedValues"]):"n/a")."<br />";
echo "eWay Full Response: ".(isset($_SESSION["eWAY_XML"])?htmlentities($_SESSION["eWAY_XML"]):"n/a")."<br /></p>";
echo "<p>UPS: <br />";
echo "Full Request: ".(isset($_SESSION["WA_Store_Cart_UPS_FullRequest"])?htmlentities($_SESSION["WA_Store_Cart_UPS_FullRequest"]):"n/a")."<br />";
echo "Full Response: ".(isset($_SESSION["WA_Store_Cart_UPS_FullResponse"])?htmlentities($_SESSION["WA_Store_Cart_UPS_FullResponse"]):"n/a")."<br /></p>";
echo "<p>FedEX: <br />";
echo "Full Request: ".(isset($_SESSION["WA_Store_Cart_FedEx_FullRequest"])?htmlentities($_SESSION["WA_Store_Cart_FedEx_FullRequest"]):"n/a")."<br />";
echo "Full Response: ".(isset($_SESSION["WA_Store_Cart_FedEx_FullResponse"])?htmlentities($_SESSION["WA_Store_Cart_FedEx_FullResponse"]):"n/a")."<br /></p>";
echo "<p>USPS: <br />";
echo "Full Request: ".(isset($_SESSION["WA_Store_Cart_USPS_FullRequest"])?htmlentities($_SESSION["WA_Store_Cart_USPS_FullRequest"]):"n/a")."<br />";
echo "Full Response: ".(isset($_SESSION["WA_Store_Cart_USPS_FullResponse"])?htmlentities($_SESSION["WA_Store_Cart_USPS_FullResponse"]):"n/a")."<br /></p>";
?>