Tienes que eliminar de /system/app la aplicacion MarketUpdater.apk (no se si se llama asi exactamente, hay dos apks del market, pues uno de ellos es el updater, borra ese)
Luego desde Aplicaciones, vas a Play Store, y le das a borrar datos. Asi debería de funcionarte, si aun asi no te va, wipeas cache y reinstalas gapps.