Retomo este post.
A mí me pasa lo mismo. El mismo mensaje de error al intentar descargar aplicaciones gratuitas (no he probado con ninguna de pago). Me ocurre desde que se me actualizó a la versión 3.5.15. He borrado datos y cache pero sigue igual.
Por cierto no ocurre cuando intento descargar alguna aplicación que aparece en la pestaña "TODAS" de la nueva versión.