Может ли быть проблема в шлюзе, когда из локалки, которая за ним одновременно может подключаться только один юзверь? Не думаю, что проблема в этом, но хочется быть уверенным, чтоб копать в другую сторону.

В iptables скромненько:

iptables -A INPUT -i lo -j ACCEPT
iptables -A FORWARD -i eth1 -o eth0 -j ACCEPT
iptables -t nat -A POSTROUTING -o eth0 -s 10.0.0.0/24 -j MASQUERADE
iptables -A FORWARD -i eth0 -o eth0 -j REJECT