Shipping zone not detected from valid addresses

I have two shipping zones, one for the Lower 48 and one for Alaska, Hawaii, and the US Virgin Islands. When I turn on Shipping Debug Mode all I see, and all my users see, is: Customer matched zone “Rest of the World”

No matter what address is entered during checkout the customer sees:
There are no shipping methods available. Please double check your address, or contact us if you need any help.

I have each US state listed individually in the regions section of each shipping zone. Why doesn’t it use the address when calculating shipping?