Click
here for instructions on setting up your Xbox.
The article fails to mention that you may need set up Port Forwarding in your router to open a tunnel to the internet for your Xbox.
The other method to use if you can't get to grips with Port Forwarding is DMZ which exposes only the Xbox to the internet, and opens up all ports.
Some routers don't support this.
Port Forwarding is the safest method as it only opens up that port, your Xbox is then protected by your routers firewall.
Microsoft have stated that not all routers work with the Xbox, here is a list of some that do work and some that don't work.
These lists are based on preliminary testing and subject to change without notice. I found this list on the Xbox forum.
Asante
FR3004C
Belkin
F5D5230-4
CompUSA
Cable/DSL Router
Dlink
Dl704
Dl707
Dl804
Linksys
BEFSR11
BEFSR41
BEFSR41
BEFSR81
BEFSW11S4
NR041
Melco/Buffalo
BLR2-TX4
Netgear
FM114P
FR114P
FR314
FVS318
RP614
Siemens
SpeedStream SS2602
SMC
7004ABR
7004VWBR
ZyXel
Prestige 310
Prestige 944
Don't Use These Routers with Xbox Live as they are currently unsupported.
If you find your router in the list below then check for a firmware update.
Netgear
FR114P
MR314
MR314
RP114
RP334
RP334
RT314
RT314
RT311
RT311
SMC
7004VBR
ZyXel
Prestige 314