It's got to do with data packets being filtered or misdirected.
I'm assuming you're going through a router, although a dsl modem can sometimes cause the same issues, since it has a router built in. It's usually just the router though.
You need to access the router, since usually the application you install from the disc that came with it will not have the options you need. You can check before doing this to be sure, just look for features I describe.
Going to put this kind of basic to be clear, so don't think that I'm talking down to you. A lot of people need to know this and I'm sure they'll check in here.
For example, if you use a Linksys router, you would input on the browser address bar: 192.168.1.1 and enter. The IP address you put in there is the one your router uses, aka your Gateway. If that IP isn't the right one, you can find this info pretty quickly in a web search, or if you know how to get your pc's IP info, you would look for the "gateway" and that will be the number.
After you do that, you'll probably get a login of some sort, user and password.
It's usually ADMIN (user) and ADMIN (password)...or even just ADMIN password and no user...maybe ADMIN and PASSWORD...again, a quick internet search will get you that info, just search for your router make/model.
It's always a good idea to back up your router settings at this point. Probably under administration or something like that. Always good to back up so you can return, just in case. What we're doing here isn't anything to be worried about though.
Once you've gotten access to the router, look for a tab or heading for something along the lines of "applications and gaming". You may just have to explore a bit. You're looking for an area for "DMZ". We want to assign your 360 to the DMZ, which means ALL ports open (applications communicate in/out of your computer/360 by going through ports. HTML normally uses 80 for example, your 360 uses TCP/UDP 3074 and 88 IIRC. What we're trying to do here works without you having to worry about the number of those ports.
Find the DMZ. You'll probably have a checkbox to enable it, and then a box to put in either a MAC address (a unique number identifier for any network device) or an IP address. I'm hoping you can input a MAC address since it's the easier route. If you do not have that, let me know.
Now look at your 360. On the back, you'll see a MAC address, or you can go to the dashboard, System settings tab, Network Settings, Configure Network. Go over to the Additional Settings tab, then Advanced Settings (do NOT restore to factory defaults below that LOL).
In Advanced Settings, you'll see your Wired Mac Address. Write that down.
If you're using the wireless adapter, it should be under wireless information. The wireless adapter has it's own MAC address, which is what you would need for this rather than the wired MAC.
Back out without saving anything.
Take that MAC address and go back to your router interface and put that in the DMZ MAC address destination. What that means is that the device you input there is completely outside of any firewall filtering, all ports are open. You do not want to put your pc in there of course, but for a console it's perfect.
*If you cannot put a MAC address in there and it only allows you to put in an IP address, let me know*
We would need to assign a static IP address if there is no MAC address input.
This is faster and easier than "forwarding ports" that some people do.
Save your settings on the router. Go back and check to be sure your DMZ setting is in there.
Boot up the 360 and test again. It should connect and not give you any messages if this is done correctly.
Things that might come up:
--Router might not accept MAC addresses for the DMZ, although I think most do now. Possible it could require an IP address, which means we would need to assign a static IP address (doesn't change, unlike using DHCP) and then put the static IP address in the DMZ
--If this doesn't work (do it again to verify before going any further) and you're on DSL, then you may have to access the modem like you did your router. There would be settings in there to open up the internal router for gaming. Most likely it would have a drop down box where you could select Xbox Live or something like that. If ports on the DSL modem are blocking packets, then it doesn't matter if your router is wide open for the console.
Doesn't really take long to do this, just takes getting familiar with the router more than anything.
AFTER that is all done...(not before, one thing at a time)
This is something else everyone should consider doing.
Go back into the router and look for a QOS setting (quality of service). Sets up similar to the DMZ: MAC address or IP address.
Put your MAC in there and set QOS to Medium (first) or High (later if you want).
What this does is to give your 360 priority over other network devices for bandwidth. If you have a console online and a pc boots up and goes online, you may have lag or disconnection...whatever. QOS lets you prioritize the device that you want to have the best service. Set the console with higher priority and then if the wife gets online somewhere else in the house, it shouldn't affect your console's connection. Most commonly used with VOIP phones to prevent dropped packets and hence poor communication quality. With gaming consoles it's a marriage saver.

Anyone who hosts games online should do this, in particular.