unfortunately, paypal does make changes to their API from time to time without notification that can cause things to stop working.
If you are using Payments Pro US as the gateway, add the following code to the checkout failure page to get the full request and full response from paypal for troubleshooting:
<?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 />");
?>