Por favor assegure-se de ter o seguinte no arquivo /etc/sysctl.conf:
net.ipv4.ip_forward = 1
net.ipv4.conf.default.rp_filter = 1
net.ipv4.conf.default.proxy_arp = 0
net.ipv4.conf.all.rp_filter = 1
net.ipv4.conf.default.send_redirects = 1
net.ipv4.conf.all.send_redirects = 0
Verifique também as regras do seu firewall, você precisa ter esta regra:
iptables -t nat -A POSTROUTING -o eth0 -j MASQUERADE
Boa sorte!