make sure you have uPNP (Universal Plug and Play) enabled on the router, if it is and its still doing it set up rules for the Xbox within the firewall on the router to open all the ports needed for live to the device.
If there are 2 xbox's the latter option will have issues as you can usually only open ports to a single device. So one will still have issues. If the router gives you the option to open to any internal device use that and all should work fine.
Xbox LIVE requires the following ports to be open:
Port 88 (UDP)
Port 3074 (UDP and TCP)
Port 53 (UDP and TCP)
Port 80 (TCP)
Note If you cannot chat with someone using Video Kinect, you might need to open port 1863 (UDP and TCP).
Taken from here:
http://support.xbox.com/en-GB/xbox-live/connecting/network-ports-used-xbox-live