A mi me paso también una vez el mismo mensaje y el problema no era falta de espacio, sino que en el teléfono había quedado un fichero .odex de una instalación anterior (creo que se creó con lucky patcher). Borrando el fichero, se instaló la aplicación sin problema.