Согласен!. У самого так работает в некоторых конфигурациях. :-)

Проверь правила по умолчанию для цепочек INPUT и OUTPUT.
Выход в мир на самом сервере(шлюзе) нормально работает? Если, да, то предложенный вариант решения доложен, по идее работать.
Посмотри трассу на компе с которого выходиш в инет. DNS сервера прописаны? Шлюз по дэфолту прописан на твоём роутере?
По поводу настройки и работы iptables, советую почитать вот Руководство по iptables