It sounds like the get payer profile behavior is not returning the shipping address.
Add a var dump of the session on the failure page:
<pre>
<?php var_dump($_SESSION);
?>
</pre>
then view source of the page and copy the code, this will give us all of the info sent to the shipping provider and paypal.
This may contain sensitive information that should be removed before posting here.