Lion won't give out DHCP addresses with Internet Sharing
I finally figured it out.


You said your Firewall is off. You should double-check. This will definitely cause Internet Sharing to not work. System Preferences -> Security &amp; Privacy -> Firewall.
In the "Sharing" panel, change your Computer Name to something simple. Instead of "Elliot's MacBook Pro", use "MBP".

Turn off Internet Sharing (if it's on). Make sure you have set "Share your connection from:" to "Ethernet", and "To computers using:" to "Wi-Fi". Change the "Wi-Fi Options..." and save.

If that didn't work: Turn off Wi-Fi on your Lion Mac. Make sure you have internet access from Ethernet, and that it works (test a site in a browser).
For your Wi-Fi connection, set "Configure IPv4" to "Using DHCP". In the "DNS" tab, delete any existing entries.


Hope this helps!