Since Emsi closed this "resolved" (but not resolved at all) thread, I will start a new one as all of us are still looking for a solution.
For some reason WooCommerce arbitrarily tells customers there is no available shipping method for their order. I have received numerous support requests from people making small, normal purchases (like a bottle of hot sauce and a 2oz bag of pepper flakes). It has proven very difficult to troubleshoot since even when using their account info, shipping/billing info and the exact same cart contents I can't replicate the issue. I have tried all suggestions on the old thread but my settings were already the way they suggested changing them too.
I have found a temporary workaround by setting the fallback shipping price to $10, but this isn't fair to the customer (who may actually have a much lower shipping price) or the client (who may have a much, much higher shipping cost).
We are using the WooCommerce USPS extension, the originating location is New York and so far most of the support request have come from people living in neighboring states, like Maine and New Jersey. Box dims and weights are set for all products as well as shipping box dims and weights set in the USPS extension up to far larger than the failed orders.