Se você não tiver um servidor DNS que esteja ciente dos nomes de host das máquinas linux, não há como o servidor DNS resolver o nome do host para o endereço IP.
Parece que seu servidor DNS no roteador aceitará registros de nome de host, portanto, você pode fazer o seguinte.
Em cada uma das caixas debian linux, edite:
/etc/dhcp/dhclient.conf
e adicione a linha:
send host-name "hostname";
Isso informará ao servidor DNS o nome do host e, portanto, ele deverá adicioná-lo à zona dns local.