I don't have an XBOX, but I will try to help.
If you think it is a bandwidth problem, try connecting at off peak hours. If you still can't connect at 3 AM, then it is highly likely that you are being blocked and it is not a bandwidth/priority problem.
When you are connecting to the XBOX live server, does it give you a server name such as "livesever.xbox.microsoft.com", an ip address like "127.0.0.1" or anything like that? If you can find out the ip address or hostname of the server your xbox is trying to connect to, you can test the connection with a computer.
For instance, if you have windows XP you can click on
start, then
run and then type in
cmd in the window and press enter. A black screen should pop up.
From there you can use:
nslookup (severname)
ping (server name / ip address) [A utility to determine whether a specific IP address is accessible]
or
tracert (servername) [this displays connection route from your computer to whatever server destination you type in]
Try playing around with these in the cmd window.
type
ping
www.yahoo.com
nslookup
www.yahoo.com
tracert
www.yahoo.com
to see how they are supposed to work.
If you are using a router you can simply fire up xbox live, log into the router and look at the active connections.
You might want to PM astroglide and bring his attention to this thread. He is a network administrator and he deals with networks for a living. I don't know much about the xbox live protocol and I don't know how much help I can be in this situation.