This is Ren from the Shopify support team, thanks for your post.
I'd start by double checking the location of the customers trying to check out, do they all appear to be in the same place or from all over? This can hint at something not lining up with your rate locations in your Shipping settings.
The second thing to check is the content of the cart. Do those products have weights assigned to them? Are they listed as "product requires shipping"?
Are your rates listed as manual or are you using carrier calculated rates? Feel free to drop a screenshot of your Shipping Settings and I can have a closer look!