Eu tive exatamente o mesmo problema com o Debian no Cubox.
Examinar o arquivo de log no servidor DHCP (executando o dhcpd OpenBSD) revelou, no entanto, qual era o problema no meu caso:
Oct 4 08:45:04 gateway dhcpd[22743]: Both dynamic and static leases present for 192.168.1.2.
Oct 4 08:45:04 gateway dhcpd[22743]: Either remove host declaration 192.168.1.2 or remove 192.168.1.2
Oct 4 08:45:04 gateway dhcpd[22743]: from the dynamic address pool for 192.168.1.0
O erro que cometi foi atribuir endereços IP estáticos a alguns hosts com base em seus endereços MAC e, em seguida, ter os mesmos endereços IP disponíveis no pool dinâmico (a parte do intervalo no servidor DHCP).
Espera que isso ajude os outros.