Se hubiera arreglado desconectando la corriente COMPLETA durante unos minutos. Luego la conectas de nuevo y anda. La razón de esto es que tienes que obligar a la consola a perder el "ticket" de conexión de XBOX Live (Kerberos 5), porque por alguna razón se había corrompido. A mi me ha pasado también y no conseguí ayuda en ningún lado, así que usé un sniffer de red (Ethereal por ejemplo) para encontrar el problema.
Todos podéis probar esto. Medid el tiempo que tarda la consola en conectarse al Live. Luego desconectáis la corriente, esperáis 10 minutos, volvéis a conectar y medís de nuevo. La primera vez que se conecta y tiene que pedir el ticket, tarda como 5 segundos más.
Saludos,