А у Вас включена маршрутизация пакетов?
Проверьте значение net.ipv4.ip_forward в файле /etc/sysctl.conf:
sysctl -a | grep net.ipv4.ip_forward
На чистой установке Ubuntu Server этот параметр будет равен 0. Надо изменить на 1:
sudo echo «net.ipv4.ip_forward = 1» > /etc/sysctl.conf
После перезагрузки должно работать. Для изменения "на лету" делаем:
sudo echo 1 > /proc/sys/net/ipv4/ip_forward
Ещё по теме:
NAT и iptables (Как раздать интернет через вторую ... 
