Why can't my customers complete checkout due to shipping address issues?

[mrsloki]

When checking out, when after a customer enters their address and phone number for shipping and clicks enter, it takes them to the next page and the page says that their order CANNOT BE DELIVERED TO THAT ADDRESS!!!! I triple checked the zones and my delivery options and EVERYTHING IS CORRECT. Please help I lost upwards of a hundred sales ALREADY!!!!!!!!!