Qualche tempo fa Microsoft ha scritto una KB per il troubleshooting dei problemi su Xbox Live.
Sono spiegate le porte che usa Xbox Live (quindi quali dovete aprire sul vostro Router) come settare gli IP, ecc...

Sperando possa essere d'aiuto a qualcuno, ripropongo il link:
http://support.microsoft.com/kb/908884/ (questa è con il terribile traduttore automatico)
http://support.microsoft.com/kb/908884/EN-US/ (questa è in lingua originale)

Qui invece c'è la KB su come abilitare la Condivisione Connessione Internet:
http://support.microsoft.com/kb/306126/