Что-то такое встречалось при шлюзе на Alt-4 и клиентах Alt-5 и выше.
При условии, что перечисленное в посте ruslandh исправно настроено, попробуйте покрутить в файле /etc/net/sysctl.conf параметры
net.ipv4.tcp_window_scaling
net.ipv4.tcp_syncookies
= 1 или = 0
Изменить параметры и рестартануть сеть.
Или вживую - echo '1' > /proc/sys/net/ipv4/tcp_syncookies
Предварительно посмотреть действующие значения:
cat /proc/sys/net/ipv4/tcp_window_scaling
cat /proc/sys/net/ipv4/tcp_syncookies
PS. толком не вникал, что эти параметры делают, но после изменений работало. Но, возможно, у Вас не этот случай...