La première question serait: quel réseau, quelles machines ? La passerelle est un Linux, je suppose, probablement Debian, même ;) Et les autres machines ? Surtout: la passerelle a-t-elle un serveur DHCP, si oui, attribue-t-il des adresses statiques ? Tu peux déjà jeter un oeil au fichier /etc/dhcpd.conf voir comment ça marche.
Vincent