Delete line 362 where the message is now, but leave the surrounding code.
Then just place this code wherever you want the message to appear (on the cart_confirm page at the top will be just below the continue button) and style it however you want:
<?php
if ((isset($_POST["CheckoutWizard_submit"]) || isset($_POST["CheckoutWizard_submit_x"])) && $_SESSION['WAVT_confirmcart_Errors']=="" && !isset($_POST["forShipping"])) {
if (!$_SESSION["eCart1_UPS_Quote"]) {
?>
<strong>Unable to find that shipping address. Please make sure the entered address and zip code are correct.</strong>
<?php
} }
?>