I had the same problem. The following worked for me.
check for any domain files
Code:
grep domainname /var/named/*
Check for the domain in any of the following files and remove occurances
Code:
more /usr/local/cpanel/etc/commondomains | grep domainname
more /var/cpanel/phpopendomains | grep domainname
more /etc/localdomains | grep domainname
more /etc/localdomains.eximreset | grep domainname
more /etc/userdomains | grep domainname
more /etc/trueuserdomains | grep domainname
more /etc/localdomains.rpmnew | grep domainname
more /etc/localdomains,v | grep domainname
more /etc/localdomains.tmp | grep domainname
If your using a stealth dns remove the DNS entry from the visible nameservers. Wait 24 hours. try adding again.
I use Stealth so the above commands are on my stealth DNS server. I removed the entry from the main dns servers and checked they are gone using www.dnsreport.com but that the domain is pointed at dns1 and dns2. Then i added the addon again without issue and then created the zone on dns1/dns2 and all fixed itself.