Internet Sharing stuck on after 10.7.3 update
I found a relatively simple solution not involving a system restart - just bring the WiFi interface down and then back up:

$ sudo ifconfig en0 down
$ sudo ifconfig en0 up


In my case en0 is the AirPort interface of my MacBook Air.

Note that turning the AirPort off and on again doesn't work, but bringing the interface down does the job.