We are getting the error "Sorry, we do not ship to your region at this time" but can't figure out why it is happening.

The store is in Michigan, and so far we know that this happened when customers attempted to have their orders shipped to Pennsylvania and Nebraska. When I login to my account, however, I am able to successfully ship to the exact same addresses.
  • Admin|Configuration|Shipping & Packaging - Confirmed country and zip code are correct.
  • Shipping options - Only the table rate is installed, and there are no Shipping Zones designated. I've tried processing orders with different dollar amounts to see if there is a pattern related to the shipping table, but so far I am able to process all orders without issue.
  • Payment options - All payments go through Authorize.net.
  • Zones - We made sure that NE & PA zones exist.
I'm stumped. Any help will be appreciated!