Чувствую, что не хватает опыта, чтобы понять в какую сторону рыть. Упростил ситуацию до предела, далее идеи кончились:

В системе есть два интерфейса - eth0 (внутренняя сеть) и ppp0 (ADSL через pppoe сконфигурированое через pppoeconf)

Фаервал отключен полностью - (все цепочки в ACCEPT) добавлено только правило маскарада на ppp0:

iptables -t nat -A POSTROUTING -o ppp0 -j MASQUERADE

Маршрутизация включена:

echo 1 > /proc/sys/net/ipv4/ip_forward

Далее устанавливаю соединение с провайдером:

pon dsl-provider

Происходит следующее: сама машина прекрасно ходит в интернет, машины из локальной сети могут спокойно пинговать любой ресурс. А вот при попытке машин из локалки зайти на веб-сайты, например, они получают в лучшем случае всего несколько пакетов и соединение замирает. Причем пинг с этой машины продолжает проходить нормально, и можно в другом окне попытаться открыть другой сайт - тоже будет получено несколько пакетов.

Уменьшение MTU на интерфейсах не помогло.

Это точно не свзязано с DNS - разрешение имен везде происходит нормально.

iptables -t nat -L -v показывает, что на цепочку PREROUTING приходит в несколько раз больше пакетов чем проходит через POSTROUTING -> MASQUERADE. Куда они пропадают - непонятно, т.к. нет вообще ни одного правила которое могло бы их задерживать.

Система Debian 4.0 ставилась с net-install диска, из остального догружалось только то что было нужно через apt-get.
Ядро дефолтное. 2.6.18 Железо проверено - полностью рабочее, другой линукс на нем выполняет эти функции.

P.S. Если у кого-то есть хотя бы ссылки на подобные случаи - буду очень благодарен.