У меня стоит ubuntu-server, на нем поднят инет через рррое доустановил dhcp сервер который внутрь сети раздает адреса на 3 ПК и что самое интересное стоит XP SP3 - Vista - WIN7 и везде работает нормально.
Шлюзом для внутренних машин и должен быть ПК с Ubuntu и DNS (выше по ссылке написано) надо брать из resolv.conf Ubuntu и прописывать клиентам.