Our scenerio:

Were sending from NY. Our product weight is 4oz per product. When someone tried to order from the UK, they were given invalid order.

After I changed the database table to Great Britain from the United Kingdom, our shipping began to work. I did not change anything on the USPS end.

What you might want to try is create a new product. Enter generic details and set your weight to oz. instead. Try using 4oz. like my product and see if you still get the error. Also which USPS shipping are you using? Do you have international enabled?

We have national and international. For each of these you have to select your shipping (at least one checkbox).