This is probably related to your shipping api credentials and not due to any issue with paypal... What shipping settings are you using? Does the url to the failure page include a ?shipping=fail in it? Does it work if you set shipping settings to none?