A mi me pasaba lo mismo y lo unico que tuve que cambiar era que las DNS's no las buscase de forma automática, sino que se las tuve que meter manualmente.
Vete a tu ordenador y busca que DNS's tienes puestas para acceder a internet y ponle las mismas.
Y sino tienes ordenador, haz una prueba de conexión en la X360, esperate a que te diga que está todo correcto y, si no recuerdo mal, cuando vuelves a entrar a la configuración de red tendrás ahi las DNS's que la consola ha recuperado automáticamente. Apuntatelas y meteselas pero de forma MANUAL.
No entiendo mucho de esto, pero me da la sensación de que la consola intenta conectarse al live DURANTE la busqueda de las DNS's, por eso falla si lo tienes en automático. En cambio, una vez haces la prueba de conexión, como la consola YA ha recuperado las DNS's, al intentar conectarte por eso si lo consigue.
En cualquier caso es lo que me funcionó a mi. Suerte tio.