Check each of your active shipping modules.
Inside the Edit menu of each module you can see what "zone" you've associated with that module. If the customer's selected shipping address is *not* in the zone specified, that module will not be available to them. If no modules are available, they'll see something like "sorry, but we're not shipping to your region at this time. please contact the store owner for alternate arrangements."

If you set the "zone" restriction to "--none--" then the module will be available to everyone.

As for customers being "in" a certain zone, check Admin->Locations/Taxes->Zone Definitions. For each zone you have, click on the Details button and be sure you've set the right state/province/regions that apply to that particular zone.