Estou disposto a apostar que o administrador do sistema que executa o servidor DHCP do Windows está exigindo atualizações dinâmicas do DNS dinâmico. Isso significa que você precisa ter uma conta válida do Active Directory no grupo apropriado para adicionar ou atualizar registros DNS nessa zona.
Acredito que há duas maneiras de resolver isso: você pode unir suas máquinas Linux ao Active Directory usando o SAMBA e elas devem poder atualizar seus registros DNS (se bem me lembro, ser apenas um membro do domínio é o suficiente para ser capaz de atualizar as zonas de DNS protegidas) ou o administrador do Windows pode configurar uma "conta de proxy" que será usada para autenticar ao executar as atualizações seguras.
Crie um usuário do Active Directory e verifique se ele é um membro do DnsUpdateProxy. Em seguida, use a ferramenta DHCP RSAT para configurar quais credenciais devem ser usadas para atualizar dinamicamente os registros DNS.
Veja um exemplo que eu roubei emprestado do TechNet: