The "NAT" settings you need to change to "Open"
are IN YOUR ROUTER, not on the 360 itself.
Log into your router, dig around for NAT settings,
change to "Open", turn on the 360.
IF this does not work right away:
RESTART EVERYTHING one by one.
Power cycle (*unplug/replug power cord, after several seconds)
modem first, wait for all lights to be on (internet "On/Connected").
Router second, wait for all lights again.
Turn on the 360.
Worked for me, although in my Netgear router,
had to change NAT to open twice in a row.
Not sure why.