To those who may also be having this problem, we solved it / found a work around:
In Halo 2's installation directory, there is a file called xlive.ini.
Open it in a text editor and change port = 1000 to port = 2000. Save it & try running game again.
(Reason: Another program on your PC may also be using ports 1000-1008, so either find and kill that program or change Halo 2's ports).