Login to the customer account and go to My Account and see what you have for an address ...
There are a few countries that have one setting of USPS and another for UPS as USPS uses US Government definition for Countries and anything that is part of the United States - 50 states, DC, Armed Services, Territories and US Islands - are part of the United States ...
UPS on the other hand recognizes many of these places as their own country ...
To see if this is the case, install UPS and go to the checkout_shipping ... when you are on that page and see that error, does UPS give a quote?
If so, that could be your problem ...
If not, then you could have bad data in the address tables which could be an issue with your code, overrides, etc.




