June here from Shopify.
To clarify, are you seeing this message in regards to your domain name itself, your registrar name, or your physical address?
Currently the only characters that will be supported are a-z, 0-9, and hyphens. Any characters outside of this, including letters with accents, will either be reformatted or produce an error similar to the one you're describing.
Can you try removing any "special characters" and let me know if that does the trick?