Along with registering the actual domain name, you need to register the nameserver that is the authority for that domain.
You have to make sure you register the nameserver not the domain name at this step.
This is the relevant section at netowrk solutions:
This form is used to register or modify a name server within your domain name. Only the administrative or technical contact associated with a domain name may request the creation or update of a host in that domain. Submit to mailto:HOSTMASTER@NETWORKSOLUTIONS.COM.
Possible Actions:
You may replace the coordinator, change host IP address, or change host name.
links to this form: http://www.networksolutions.com/cgi-bin/makechanges/itts/host
I am not sure if anyone else lets you do this registration. Check with the company that registered your domain name.
