@Joseph I've seen this error before. It can be due to an error or odd symbol in the address, or their state/country isn't available for the shipping methods you have set up.
For example: we ship certain hazardous materials, and we have those items tied to shipping methods using UPS Ground. If someone who can't use UPS Ground has one of these items in their cart, they will get that message, since there are literally no options available.