Si usas proxy, este problema es típico, prueba descargar las aplicaciones via Wifi o via datos a ver si se presenta el problema en todos los casos, si es asi entonces:
Ve a Ajustes/Aplicaciones (o administrar aplicaciones) vas a la pestaña "Todos" y aqui deberás entrar dando un tap en cada una de las aplicaciones mencionadas abajo y para cada una de ellas darle al boton de eliminar datos y tambien al de eliminar cache.
Google Play Store
Framework Google Services o Marco de servicios de google
Chrome
Reinicia de nuevo tu teléfono.
Prueba y me dices, suerte!
