¿Como tienes conectada la consola al PC?, ¿por cable cruzado de la xbox a una tarjeta de red en el PC?, ¿qué S.O. estas usando?.
Me voy adelantar un poco pensado que es asi y que estas bajo Windows XP, vete a Inicio - Configuración - Conexiones de red
Desde alli seleccionas la conexión que utilizas para xbox-pc y le das botón derecho - propiedades.
Ahi vete a la pestaña de "avanzadas" y en "conexión compartida a internet" marcas las casillas correspondientes, aceptas todo y tendría que funcionar (o en todo caso reinicia).