Domain Mapping error: Domain name is unavailable to access

When I try to map one of my add-on domains to my subdomain, it gives me the following message in a red box:

Domain name is unavailable to access
We can’t access your new domain. Mapping a new domains can take as little as 15 minutes to resolve but in some cases can take up to 72 hours, so please wait if you just bought it. If it is an existing domain and has already been fully propagated, check your DNS records are configured correctly.

What am I doing wrong/how do I fix this?