You know, I was thinking about it today, and I recalled I forgot to tell you you had to set up IP Masquerading for your Ubuntu machine. What this does is that when packets come into the Ubuntu machine, it alters the headers so to machines on the Internet, it looks like the packets came from the Ubuntu machine. It tracks these connections, so when it gets a response, it sends it back to the right machine on the LAN.
Anyway, if you are using a firewall like Firestarter, that will have something built in that tells you how to do the IP Masquerading. If you just want to use netfilter/iptables, the command would be something like:
$ sudo iptables -t nat -P POSTROUTING DROP
$ sudo iptables -t nat -A POSTROUTING -o eth1 -j MASQUERADE
The first line says, the default policy of this chain should be to drop any packets.
The second line says that any packets destined for the eth1 (Internet) interface need to be masqueraded first.