This is part of the problem is the order that it all occurs in. After you fill in the checkout form do you go to the confirm page or are you going straight to PayPal? If you are going to the confirm page then you can add in the USPS shipping quote server behavior to this page. After you have added the server behavior you need to check in the cart object to ensure that you have the shipping charge rule for USPS.
If you are going straight to the PayPal site then you will need to gather the zip before this page and have the shipping quote server behavior occur before the checkout like on the cart page. Please post back with this info and how you currently have it setup so we can help you get it worked out.