I have been trying to repair this problem for several days now and pulling my hair out. Customers are receiving the following error when on the check out page:

We are unable to find a USPS shipping quote suitable for your mailing address and the shipping methods we typically use.
If you prefer to use USPS as your shipping method, please contact us for assistance.
(Please check that your Zip Code is entered correctly.)

I have installed the May 2008 update and have looked at all other shipping settings and cannot figure out why this is still happening.

We need to enable basic international shipping methods as well as domestic. Neither will work at the moment and USPS is what we use.

Can someone explain step-by-step what to check?