These error messages can appear if the domain because of the following:
1. The domain is not returning a valid SOA.
2. The domain is not returning valid nameservers prior to Cloudflare (you can't just add the Cloudflare nameservers to get around this). The domain must be returning the nameservers active at your registrar **prior to Cloudflare.**
3. Your domain must be resolving.
You must contact your registrar for assistance with these items. Cloudflare can not manually add domains in any circumstance.
Note about "Not a registered domain":
If your site isn't returning a SOA record, or if the domain isn't being picked up in whois, then you need to make sure your site has name servers attached to the domain. You should check with your registrar to make sure an SOA is returned, or add the site to a service like DynDNS so that name servers and an SOA are returned in the lookup.