I've experienced a failure of internet sharing and attempted all the solutions in these forums without success.
Finally, after long investigating the problem, I've foud the culprit and a solution.
What happened to me was that activating internet sharing from ethernet to wi-fi made the latter interface the one used as default route (which, of course, made non sense).
I'm not enough expert of OS X networking to offer a permanent fix (I still can't understand what's exactly goes on with IP Monitor Agent and all its friends), but here is what you can do (from the terminal) to fix it evey time it fails.
First of all, before activating the sharing, note your default route, type
netstat -nr | grep default
and take a note of the IP address reported after "default" in the line returned, say it is 192.168.1.254. Then activate the sharing and issue the following two commands
route delete default
route add default 192.168.1.254
where you replace 192.168.1.254 with the IP you actually noted before.
Hopefully some OS X networking expert will tell us how to make it permanent (and why the default route is set to the wi-fi in the first place).