To connect to XBox Live you must have an open NAT, if you don't then you'll get errors when you try to connect to the XBox Live service.
At times the XBox will read that you have an open NAT if your router allows uPnP, however, this will be falsely reading this variable.
There are two ways to fix issues connecting to XBL:
1. Open UPNP for your network
2. Port Forward.
The first is rather self explanatory, on Linksys routers simply go to the administration page and turn uPNP on (and the varaious options for it).
The second is quite easy as well, simply assign your XBox a static IP (I believe you can do this in the xbox settings, or assign its MAC address an IP from within your router settings); from here simply go to "applications and gaming" (aka Port Forwarding) and forward:
Now you should have no issues connecting to XBox Live or (more specifically) Halo 3.
This information has been provided by Microsoft Help and Support - Xbox 360: Port settings for Xbox Live