Eso suele ser porque tienes los DNS's configurados en automático (obtenerlos del ISP). Infórmate en tu ISP cuales son los DNS's y configuralos manualmente.
Lo mejor que puedes hacer (si segun tu no tienes mucha idea, por lo que no voy a empezar a contarte lo del ipconfig, etc...) es poner en la configuración de la X360 que te detecte automaticamente las DNS's. En principio asi te tiene que funcionar.
Una vez hecho esto te vas a configuración y te apuntas las DNS que te ha detectado automaticamente la consola solita. Le dices que lo que quieres hacer es meterle las DNS's de forma manual y le metes los mismos numeros. Con esto cada vez que arranques la consola no se pondrá a buscar DNS's, con lo que te ahorraras mas de un problema .
Lo de que siempre tengas que hacer la prueba para poder entrar al Live me pasaba a mi tambien, y poniendo las DNS's en MANUAL ...mano de santo. Te lo recomiendo