This problem often occurs because it's not clear that prostores is looking for the two-letter word state code instead of the full name. Change the state input field to a dropdown list instead. The prostores ssml code to do that is:

source="$system.states('US')"
selected="$store.state"/>

This should replace the following code on your customer registration template of the effected store:

If customers are in fact entering in the proper two letter state code, and it still says the zip code is bad, you can export the zip codes from the system (go to admin->support->export area...)