First off, are you using a wireless router or just plugging your Xbox into the internet?
It could be your firewall, as stated above, or if still it does not work, you have to change the MTU settings.
The maximum transmission unit (MTU) is 1500, but for the Xbox 360 it must be set within the range 1364 – 1492.
So access the router setting on your PC and set it within the range 1364 – 1492 or call your ISP or router manufacturer to assist you doing so if you do not know how to access to your router settings (see below).
However, large packets can block up a slow interface for sometime, increasing the lag on other packets so it’s better to be set to the lowest possible MTU, Which is 1365.
How to access your router settings:
The way to access to your router settings differs from one router to another but basically it will always be through your PC most of them would be as follows:
1. Open an Internet Explorer page on your PC.
2. On the address bar, type 192.168.1.1 for Netgear routers, 192.168.2.1 for Belkin routers or 192.168.1.1 for Linksys routers. If you have even any other brand you can try these three numbers I reckon one of them will work.
3. Then you click GO.
4. You'll get your router settings main page on the screen asking you for your username & password usually by default the password will be even the same as the Username (Username: admin, Password: admin) OR it will be password (Password: password).
5. You can there look for MTU settings, it differs from one router to another you can just look for it then set it to 1365 as we said before.
(Source:
http://xbox360help.blogspot.com/2007/03/mtu-failed-on-xbox-live-test.html)