I for the first time this evening had to enroll a DNS server in some custom app partitions at a customer site. I've never actually done this before, though I knew it was a simple dnscmd command. I ran what I felt was the obviously correct command a couple times and got this error, DNS_ERROR_DP_DOES_NOT_EXIST. The name of the switch is "EnlistDirectoryPartition" which I mentally translated to mean I needed to supply the DN of the direction partition I wanted to enlist. This is in fact wrong if you take the time to read the help. You need to supply the FQDN of the directory partition. Totally unintuitive if you ask me, but whatever works.
So, if your NC is DC=CampusDnsZones,DC=BrianDesmond,DC=Com, the command to run is dnscmd MyDnsServer /EnlistDirectoryPartition "CampusDnsZones.BrianDesmond.Com".