It sounds like an NAT issue. You should all run XBL connection tests from the Dashboard (Settings > System > Network Settings, and then pick which connection type you have) to see if anyone has a Moderate or Strict NAT.
An Open NAT is the way to go, so if you have a Moderate or Strict NAT, you'll have to forward ports 88, 3074, and possibly 53 and 80 on your router. You could put your 360 into a DMZ if you don't want to bother with opening individual ports, but that doesn't always work for some people. Sometimes simply enabling UPnP also works, but again, your mileage may vary.
http://portforward.com/english/applications/port_forwarding/XboxLive360/ is a good resource for learning how to do this. Note that the guides on there say to also forward port 1863, but you don't have to do that unless you're also having problems with MSN Messenger (or whatever it's called these days) on the 360. --- If at first you don't succeed, try, try again. Then reload.