There is a very similar thread with several solutions to exactly the same issue you are facing, please take a look.
Are the products in your cart in the same Shipping profile as your domestic rate?
Products can only be part of one Shipping Profile and then multiple regions and rates can be applied to this specific profile which applies to those specific products
Hi, we have reports of this error happening in our store every so often including today. It doesn't have anything to do with our settings because
1) It only happens to some customers occasionally, but works most of the time for everybody else.
2) It often is "fixed" by the customer trying it in a different browser.
For instance it will say "We don't offer shipping to New York" when a customer is trying to buy a product, but we'll just have sold 20 of the exact item to other customers in New York, and the customer who has the problem will be able to buy it by switching from Chrome to Firefox.
We've seen this happen at least 10 times randomly over the past 6 months, and I feel like it's safe to assume it happens more than we know about because most customers won't report it