Hai verificato che le password sulla macchina debian non siano cifrate in MD5. Se non ricorso male, alla configurazione del pacchetto shadow, ti viene chieste se vuoi o meno attivare MD5. Se lo fai allora perdi la possibilità di usare NIS.
Ciao, Giuseppe