I thought I would post a link to a guide that I Found after I had so much trouble getting everything to work. The way I have my 360 to connect to live is by connecting it through the ethernet port to a spare laptop I have. The laptop then connects to my wireless network and I can get on to live.
I originally had it setup through ics or internet connection sharing which is the easiest way to get it to work, however I was running into some problem with NAT when trying to connect to games on halo 3. My nat was showing as either moderate or strict instead of open which wouldn't allow me to connect to private games, and caused my matchmaking to be really slow.
This guide shows you how to get everything connected except through creating a bridge connection. Once I did this, and did some troubleshooting it changed my NAT settings to Open and I can connect find.
At first it wouldn't work, but I followed the troubleshooting tips below the guide and forced my wireless card into promicious mode and everything worked find. So if you have your 360 setup through your laptop and are getting nat error messages take a look at this guide:
How to setup bridging and troubleshooting tips:
http://www.xboxlivetheguide.co.uk/XBoxLiveTheGuide3.php?title=How%20do%20I%20setup%20Bridging