A configuração do seu cliente Linux precisa ser atualizada. Adicione a seguinte linha
send host-name "hostname";
ao seu equivalente de /etc/dhcp3/dhclient.conf. (É aí que o Debian armazena o arquivo de configuração do cliente DHCP.) Isso dirá ao servidor DHCP o nome do host do seu cliente Linux. O servidor DHCP deve agora configurar as entradas de DNS apropriadas para o seu cliente Linux.