I'm trying to change nameservers for some of my domains at GoDaddy, but I occasionally run into "Nameserver not registered" problems, and then I'm not allowed to set the nameservers. Here are the cases I've tried, and I still don't understand what it takes to have a registered nameserver.

With ns1 and ns2 pointing to my nameservers, I can set the nameservers successfully when I set up domains as follows:

Host Summary entries for ns1 and ns2 at GoDaddy
.co.cc domains with A records for ONLY ns1 and ns2
Hosted with other nameservers. Have only A records for ns1 and ns2

But these do NOT work (nameserver not registered error):

.info domains at GoDaddy with A records for ONLY ns1 and ns2
Hosts with dyndns.org that point to IP of nameservers

Also, when I dig any domains hosted at my nameservers using any of the above, I get the correct response. So what's the deal here? Why do the last two cases get "nameserver not registered errors"? Thanks!