I'd love to help you get to the bottom of this. In order to do so, we will need more context regarding the exact issue your customers are seeing on their end in order to isolate any potential causes.
1. Do you have any screenshots of what they are seeing on their end when going to pay at checkout? Specifically, any available shipping rates along with the addresses that they are entering. The most common issue is they have a shipping address that is not included in your shipping zone.
Eg. The merchant is trying to have their order shipped to Detroit, Michigan. However, in the Shipping Zone settings, Michigan is excluded from the list of states that you ship to.
2. The other issue could be based on the weight/cost of the order. This is common if you have created manual weight/price based rates.
Eg. You have three weight-based rates set up: 0-1lb is $5 - 1-2lb is $7 - 2-3lb is $10. But if their order total weight is 3.1lb+ they will not have an available rate at checkout.
If there is anything else I can help you with, please let me know.