So you did something wrong then, Rico. It's the same procedure, no matter what kind of Gateway you're using. If it can NAT a windows PC, it can NAT a linux box. Just set the default route (route add default gw [router's IP]), done.
I really recommend you guys to read some linux book, no matter if ebook or a real paper one, it's really nice to understand the essential stuff. No matter what distro you're using, the SuSE book from the professional packages are pretty good (you can buy older suse distros for just a few bucks, so while you throw away the CDs/DVD keep the book).
Or, if interested in more special stuff like debian's apt or other distro-dependend stuff, just buy an appropriate book, you won't regret it.