Hola. No creo que sea por cambio de operador. Si no te importa cambiar de rom, haz backup de tus datos/lo que quieras, instala p.e. la de jrsoft y mira si se arregla. Tb prueba a instalar la última versión del market (3.4.4 creo) a ver si se resuelve.
Es lo que se me ocurre y lo que yo haría.
Tb puedes acceder al market por Internet a ver si te reconoce el nexus dentro de tus dispositivos.
saludos