What's your operating system?
In Windows '98 SE and Millenium, I always had trouble with the Microsoft Internet Connection Sharing wizard (i think that's what they called it). The thing would work great, then not work great. I'd check all the settings find no problems, remove and reinstall it, and then it'd work great again. Basically pretty buggy IMHO. If you are running these versions of Windows, I would suggest that you go ahead and get a hardware router/firewall.
If you are running XP, I've had NO problems with the NAT server (Internet Connection Sharing) in it. If you have it turned on, then generally other computers running XP will automatically recognize how to connect to the internet and do it. If they do not have XP, or if they do but it is not working on its own, manually set their TCP/IP configuration to the following:
IP (static): 192.168.0.2
Default Gateway: Your computer's IP
Subnet mask: 255.255.255.0
That should do it, and no need to spend any money.
'98 Camaro SS: Incon twin turbo. Sold
'99 Camaro SS: Heads/cam/bolt-ons. Sold.
'91 Camaro RS: Stock.
2010 Camaro SS: Hell yes.