Thanks guys! Had the same issue, found your posts via Google, worked like a charm. I registered on this forum for the sole purpose of thanking you. You've made this world a better place.
If anyone else is trying this, you can find Internet Connection Sharing by doing:
Start button -> Settings -> Network Connections
Right-click the appropriate connection (likely your Wireless one, duh)
Click the "Advanced Tab", and check that first box.
Reboot laptop & Xbox, make sure they're connected with a CROSSOVER ethernet cable (not the regular kind), and you should be good to go. This really rocks - you just transformed your laptop into a $110 peripheral for your Xbox.