Could be your firewall not allowing the ports needed through or forwarding them to your xbox.
You might get a "Strict NAT" error.

I also turned off UPNP on my modem, and they gave all sorts of issues, so check thats turned on too.