Here's an interesting experience with ICS and routing. I've read all the related threads about ICS and linux setup and didn't see this come up before. Most of my setup worked, except for internet access. I have the following setup:

There is a cable modem and a wireless router downstairs.

Upstairs is the local network.
Windows XP machine with wireless card is connecting to the internet via the broadband router. The machine has a an ethernet card as well for the local network. I enabled ICS for the wireless connection, no firewall.

Next to it there's a Fedora box with an ethernet card connecting over a crossover cable to XP. It obtains an IP address from XP but cannot see the net. I can ping the wireless interface on XP, from the Fedora box. However I cannot ping the router interface 192.168.1.1 from Fedora. I believe that's the main problem. Consequently I cannot ping the address for google or yahoo. I think that pinging the router gateway is required though.

Some more info. On Fedora, I have the eth0 interface set up with dhcp client and it pulls address 192.168.0.70. The XP local interface is set up by ICS to be 192.168.0.1, as expected.

SO WHAT THE HECK COULD HAVE BEEN WRONG?

Well, I looked again at the protocols for the Local Connection in XP. One funny little guy was my VPN protocol (the client wasn't even running) CheckPoint SecuRemote. Just out of curiosity I disabled it. Wham! the ICS started working properly right away...