Pues yo he borrado los datos del Play Store, he desinstalado las actualizacion del Play Store (ahora vuelvo a tener el Market, pero al menos tengo algo) y he borrado tambien los datos de Marco de Servicios Google. Posteriormente he reiniciado y solucionado!!! Al menos de momento...
Para borrar los datos (ajustes - aplicaciones - administrador aplicaciones).
Un saludo!!