The user sets the shipping address when they are on the paypal site, this shipping address is then transferred back. It could be a problem with the sandbox. have you tried doing a live transaction?
try turning the sandbox off, create a product for 1 penny, get live api credentials and see if the shipping is working that way. the shipping rate will be returned on the pp_confirm page before the customer can place the final confirmation of the transaction, so the transaction does not need to be processed to test if the shipping is working, but if you tet all the way through, that is why we create 1 penny product.