Que internet usa? Discada? ADSL? Cabo? Qual a configuração do micro que esta ligado à internet?
Porque provavelmente faltam apenas algumas regras de iptables para disponibilizar a internet na rede, mas para isso precisamos saber qual é a internet, em que placa de rede esta ligado a internet, em que placa esta ligado a rede, e etc.