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.
I'm having similar issues trying to register for UPS labels. It says my address is not valid because it's a POBOX or my phone number format is incorrect. But everything is correct. My address is a regular address and I have even tried another business address and still same issue. I tried all cap, and nothing.