I'd start by clearing the system cache (it's just updates plus other temporary files, nothing that's at all important to anyone) by:
1) Tap the silver Xbox Guide button on the controller, go right 2 clicks to Settings, pick System Settings.
2) Select Storage (or Memory).
3) Move over any hard drive or memory unit (not the Cloud) & press (Y) on your controller & pick Clear System Cache.
4) When asked to confirm storage device maintenance, choose Yes.
Some NAT problems are subtle and don't appear in the Test Xbox Live Connection test. Most likely there's a port blocked... ports can be blocked in your router, modem, or at your ISP. Since the Xbox 360 uses different ports than PCs & Macs use, you can't
see the effect of a port blockage except on the Xbox.
A sequential power cycle is the first step in clearing a port blockage:
1) turn off the Xbox then
2) unplug the power from the router (Some folks have a combination modem-router AKA 'gateway'. If so, skip step 3).
3) unplug the power from the modem.
4) Wait at least 30 secs then replug the modem (or gateway) power.
5) Wait 'til the light on the front of the modem (or gateway) which says ONLINE, READY, CABLE or DSL is on solid (not flashing), then plug in the router. If
you have a gateway instead of a modem and router, then when that light says it's ready, skip step 6.
6) Wait until the WiFi light on the router is on; you may not use WiFi, but it's still a good indicator your router is finished booting up.
9) pick Delete Profile Only. This deletes the profile but leaves saved games and achievements. Now, re-download your profile.
1) Tap the silver Xbox Guide button
2) Select Download Profile (and if you don't see it, press the blue X button to make sure you're not signed in) and proceed with Profile Download.
3) Enter the Windows Live ID for your Xbox LIVE gamertag when asked.
4) Enter the password for the WLID.
4A) If your account is an Xbox LIVE child account, the parent’s Windows Live ID & password is required as well to download your profile.
5) Select the storage device for your profile (choose Hard Drive if you have one, or Memory Unit if you don't have a Hard Drive).
6) When the download completes you will be asked if you want the console to remember your password. If it's your home console, I'd say yes, otherwise I'd think carefully about leaving my profile unprotected on somebody else's Xbox!
7) Sign in, and play!
Did this solve your problem?
Sorry this didn't help.
Great! Thanks for marking this as the answer.
How satisfied are you with this reply?
Thanks for your feedback, it helps us improve the site.