[nznog] 'Registering' a DNS server

We've just set up a new DNS server for a client whose domain name is a .co.nz name, and we can't make it a primary or secondary for .com or .net names. In the (distant) past we've 'registered' name servers with Network Solutions, and then it's been all good. Now that the registries are with Verisign there seems to be no way to register anything other than a name server on a .com or .net name, and that has to be completed via the registrar (Tucows, Godaddy etc). I'm not sure whether I'm being particularly dense or if this is actually a difficult thing to do - can someone please let me know what the process is now for registering a .nz server to enable it to be a primary or secondary for .com or .net names. Thanks, Gerard