Je vais aussi y aller avec mon p'tit tuto. 
D'abord un schéma qui devrait ressembler à ta config pour fixer les idées.
- box<--->eth0|Debian|eth1<--->eth0|Ubuntu
On va supposer que l'ip de la box est : 192.168.1.1
Avec Debian configurée ainsi :
eth0 : 192.168.1.10 (pure hypothèse à adapter)
eth1 : 192.168.0.1
Et Ubuntu configurée ainsi :
eth0 : 192.168.0.2
Il faut activer deux choses sur ta passerelle :
1- L'ip forwarding de eth1 vers eth0 avec (comme celà a été dit) :
echo 1 > /proc/sys/net/ipv4/ip_forward
Ou de manière permanente en éditant /etc/sysctl.conf et en y mettant : net.ipv4.ip_forward = 1
2- Faire de la translation d'adresse :
- iptables -t nat -A POSTROUTING -o eth0 -j MASQUERADE
(à placer dans le script contenant les règles pour que ce soit permanant aussi).
Normalement c'est suffisant.
Si t'as déjà tout ça en place, désolé j'avais la flemme de lire les logs d'iptables.
My 2 cents. ;)