To troubleshoot the problem, add the following code to the checkout_failure.php page:
<?php
if(!session_id()) session_start();
echo("PayPal Full Request :<br />");
echo("<code>".isset($_SESSION["PP_DirectPayment_postedValues"])?$_SESSION["PP_DirectPayment_postedValues"]:""."</code><br /><br />");
echo("Paypal Full Response :<br />");
echo("<code>".isset($_SESSION["PP_DirectPayment"])?$_SESSION["PP_DirectPayment"]:""."</code><br /><br />");
echo("USPS Full Request :<br />");
echo("<code>".isset($_SESSION["WA_Store_Cart_USPS_FullRequest"])?$_SESSION["WA_Store_Cart_USPS_FullRequest"]:""."</code><br /><br />");
echo("USPS Full Response :<br />");
echo("<code>".isset($_SESSION["WA_Store_Cart_USPS_FullResponse"])?$_SESSION["WA_Store_Cart_USPS_FullResponse"]:""."</code><br /><br />");
?>
This will write the Full Request and Full Response that are sent to PayPal and any shipping provider you have selected so we can get an idea of what is failing.
NOTE: The Full Request returned will contain you paypal api information, you should remove the api information when posting it in your update.