What's your store's configuration for Configuration->Minimum Values->Post Code? The default is 4, but minimum lengths of US postcodes is 5. If the value's currently 4, try changing that to 5!