I've been having the same problems as everyone else here. Trying to share internet connection from my ethernet wired iMac to my MacBook and my iPhone. Tried all the workarounds, but nothing works, or lasts very long.
Yesterday, I finally talked with AppleCare for over an hour. All their suggestions (trashing preferences, changing settings, etc.) failed, as well. The AppleCare person then put me on hold to speak to an engineer, who told her that Snow Leopard no longer supports Internet Sharing as of 10.6.1.
Not willing to accept that answer, I had them set up an appointment at the Apple Store Genius Bar for me, and after chatting with the Genius for a while, he also confirmed that Internet Sharing is no longer supported under Snow Leopard. Apparently, there were many hardware issues that the engineers decided to circumvent, and so did not include support for Internet Sharing with the internal airport in Macs. They said that the Airport it is intended to receive, not to send a signals! Yet, it worked fine, doing just that, under Tiger and Leopard! The only fix he could offer was to wipe my drive and take me back to 10.5, which I declined.
However both the guy at the Genius Bar and the lady at AppleCare inferred that Apple "may" release another update to fix this issue, if they get enough complaints and bug reports.
So, there you have it. Apple no longer officially supports Internet Sharing in Snow Leopard.