Ajustes > Aplicaciones > Play Store; y borra caché, datos y todo lo que te permita.
Ya que eres root, podrías probar a directamente borrar la aplicación y reinstalarla (si haces esto, primero asegurate de tener la apk de Play Store, a ver si luego no la vas a encontrar...)
También se me ocurre que podría ser el adfree, que supongo que lo tendrás, aunque sería raro y no se como se podría solucionar, pero investiga esto si lo demás no funciona.
Si no funciona nada, en fin, es posible vivir sin market, simplemente descarga las apk que quieres vía Chrome, un Xperia Z puede hacerlo perfectamente.
