Parece ser que es un error reciente del Google Play, aunque no sé exactamente cual es el origen del mismo.
He encontrado por internet algún reporte que indica que lo han solucionado de la siguiente manera:
Ajustes -> Aplicaciones -> Administrar aplicaciones -> Google Play Store -> Forzar detención -> Borrar datos