Por si no queréis complicaros la vida os paso la solución que he encontrado yo:
El aviso de memoria insuficiente aunque tengas memoria de sobra viene provocado por Google Play, en algún momento ha dejado de funcionar correctamente e interpreta mal el espacio disponible.
La solución es tan sencilla como desinstalar las actualizaciones de la aplicación "Google Play" y todo vuelve a funcionar perfectamente, no hace falta ni reiniciar:
AJUSTES/APLICACIONES/ buscamos la aplicación GOOGLE PLAY STORE/ pulsar DESINSTALAR ACTUALIZACIONES
Ya está. Resuelto. El Google Play vuelve a ser el Market original pero enseguida se actualiza automáticamente a Google Play pero ya sin dar el maldito aviso de falta de espacio para instalar aplicaciones
