Pues yo acabo de poner el adaptador wifi y me pasa lo mismo, antes con cable juraría que no pasaba.
A lo mejor lo que pasa es que cuando arrancas la consola se inicia tu sesión, pero la conexion wifi para entonces aun no esta disponible y por eso no conecta, es decir, que la consola al arrancar no detecta que estas conectado porque aun no se ha conectado el wifi al router.
De hecho, he probado a deshabilitar la opcion de inicio automatico a xbox live, y lo que hace es que no inicia sesion al encender la consola, pero si la inicias tu manualmente se inicia tambien xbox live. Esa opcion no debería llamarse "inicio automatico de xbox live" sino "inicio automatico de sesion", porque es para lo que sirve en realidad.