a mi me paso algo parecido, pero eran con aplicaciones especificas, por ejemplo el system tuner pro al momento de desintalarlo y despues al rato lo instale denuevo no me dejaba me decia que no tenia espacio siendo que me quedaban como 1.4gb para almacenamiento interno, descrubri que era el problema de LuckyPatcher ya que como lo habia parchado tenia que regualizar primero eso. O sea con el programa desintalado entre nuevamente a LuckyPatcher y borro el odex parchado y despues me dejo instalar sin ningun problema.
haber si te ayuda..