Недавно было нечто похожее:
Шлюз, на Ubuntu 8.04 - server, подключенный к Корбине, имел полноценный интернет (открывались как поисковики, так и сайты). Однако компьютеры стоящие за ним, открывали только поисковики и лишь немногие сайты. Я уменьшил mtu для ppp на шлюзе до 1000, однако это не помогло. После этого я уменьшил mtu для eth0, компьютеров за ним, до 500, и все заработало. Конечно эти настройки не оптимальны и нужно все настроить по-человечески, но идея я думаю ясна: попробуй, для начала, уменьшить mtu у сетевых интерфейсов компьютеров за шлюзом.