Wowzers, this is an annoying message! I spent the better part of Three days trying to crack this for a customer!
Ok so in my scenario, I had 30 PC's coming up with this error at bootup. I think at that point its a fair assumption that there aren't actually 30 PC's all running with duplicate names sitting downstairs in a store cupboard right..?
So first port of call, check the event log. I had something like this:
The name "MYDOMAINNAME/MYPCNAME :0" could not be registered on the Interface with IP address 192.168.1.100. The machine with the IP address 192.168.1.1 did not allow the name to be claimed by this machine.
The SBS in this case was 192.168.1.10 so why is 192.168.1.1 even talking to my machine when it boots up!?
I checked the source of the problem 192.168.1.1 and at first glance couldnt find any problems but then a little more digging and we found out the issue.
192.168.1.1 was a Linux server, named exactly (yes I said exactly) the same as the Internal Domain Name. So guess what, at DHCP request time, it was going off and sourcing DNS and DHCP via a combination of Samba and Windows SBS packets.
I appreciate that this wont be applicable to everyone but when I was trying to find this error where there actually WASNT a numpty who had named two computers the same it came up dry...
By the way, another fix which might help you a little... Put your DC/GC with its domain name Domain.local into hosts and point it to the server IP... Might work?