Domain mapping issues: Domain name is unavailable to access

I’m trying to use Domain Mapping on my site, but I’m having issues setting it up.
I have set up a dedicated IP address for my WordPress multisite install and I also have a WildCard SSL certificate to use SSL with the sub domains. I have also setup Cloudflare for my WP Multisite and have added the proper records for my IP address (the domain A record for the domain I want to map is pointing to my IP), etc., and I also added the domain I want to map to Cloudflare.

However, when I go to map the domain I get an error message: “Domain name is unavailable to access”.

I tried disabling "Verify domain's DNS settings" and "Check domain propagation before mapping" in Network Admin -> Settings -> Domain Mapping and now I’m getting ERR_TOO_MANY_REDIRECTS.

What steps am I missing?