Unfortunately, right now, the address has to be in Address Complete, otherwise you will have to talk to your local postal service and get your address added. This can be really frustrating to places that do not have mail service to their place of business.
Check your address here:
If you haven't tried using all CAPS. Try that.
Or put your address into here -> https://tools.usps.com/go/zip-code-lookup.htm
It will spit out the way USPS sees your address, which should work. As stated above, this is a pretty frustrating but small fix that Shopify should prioritize to its devs. At the very LEAST, just TELL PEOPLE to try putting it in all caps or link them to the "USPS address lookup" in the error message.