It's possible that your router isn't configured to allow network traffic across the ports in order for it to make a connection with the xbox live servers.
box LIVE requires the following ports to be open:
You need to have port forwarding setup between the modem/router for the following ports.
* TCP 80
* UDP 88
* UDP 3074
* TCP 3074
* UDP 53
* TCP 53
Another way to do it is to activate Universal Plug and Play if your modem/router supports that. It can be a security risk. But it basically lets your Xbox request for the ports it needs in order to access the Xbox live servers.