I have a Dlink DI-624 (not DI-624+) rev. C2 router, and i've been having this issue. I've also noticed that whenever i try to connect to XBL, that my computers lose connectivity.
so, i've been searching this issue for a few hours already trying to get my 360 online. i'm hooked up with an ethernet cable directly to my router. Basically, whenever i go to connect to XBL, on the final test it won't connect me. i've found a few fixes, but neither of them work.
One fix is to
change the UDP and TCP settings to the following:
UDP - 88
UDP - 3074
TCP - 3074
Now, i've done that already, and still nothing.
The other is to
downgrade the router's firmware to 2.75, but i can't seem to find that one. And the link provided on that post is dead now

.
are there any other possible things i could try to try and get this fixed?
EDIT:
i've also tried hooking up my 360 directly to my modem and that's even worse. it won't let me get online! going through my router, it passes all tests until it gets to the XBL section of the test, then does what i described above.