A Windows client will first attempt to update the DNS server with an unsigned dynamic update, with a constraint that the CNAME record must not exist. The exact form of the update response is critical, the difference (additional records) between BIND and internal DNS is enough to make a Windows client fail to retry with a GSS-TSIG response.
I'm working on this for a client.
(In reply to Andrew Bartlett from comment #1) Does BIND or SAMBA generate the wrong response, or both?
Our initial diagnosis was that the BIND9 and Windows servers behaved the same, and that internal DNS had a different response. However, we have had another customer raise a very similar issue with BIND9, so we will be looking into the whole area in detail, and most likely raising additional bugs. We have some network traces (internally), and expect to take some more in that investigation stage.
I think this should just be a dupe of bug 11520. Will reopen/open another bug if this isn't the case. *** This bug has been marked as a duplicate of bug 11520 ***