Alright, well, this probably isn't the problem for you, but who knows?

For me, I have to have my XBox off, then I need to reset my modem. Once the modem configures properly, THEN if I turn on my XBox it will connect to Live for Halo 2 (I haven't tried any other games). If my XBox is on prior to resetting the modem, or if I turn it on too soon before the modem configures, then it won't work. Try that, doubtful, but who knows..