If you are getting this error, it means that you haven't used the correct state code, e.g. you used "California" instead of "CA". For a full list of state codes please refer to this article.
You can easily update your customer's address on the order page to fix this error.