Bueno amigo, aunque no soy un entendido en linux, tu problema yo lo tengo solucionado ijjijiij, aunque parezca mentira, vas a ser a la primera persona que voy a ayudar. Bueno vamos al tema:
Yo tengo en 1 ordenador Red Hat 9, en este tengo contectado el modem por usb que seria eth0 y la tarjeta de red que va conectada al ordenador de windows es eth1. Hasta ahi creo que todo sera igual con lo tuyo. Bueno, pues para hacer NAT instale un cortafuegos llamado firestarter, que ademas de servirte de cortafuegos sirve para hacer NAT.
La paquina web de este pedazo de programa es:
http://firestarter.sourceforge.net/
y el manual donde te explica perfectamente (pero en ingles) como se hace NAT es en esta otra direccion que esta en esa misma web:
http://firestarter.sourceforge.net/manual/nat.php
Yo hice exactamente lo mismo de lo que pone ahi, y claro, con mi diccionario de ingles al lado de la mesa, pq mi ingles es bastante malo.
Te aseguro que funciona, y es supersencillo, sigue las instrucciones y lo conseguiras, por cierto el otro ordenador tiene windows 2000, Un Salu2 y espero haberte ayudado.