Stesso problema.
Questo problema l'ho notato da quando ho ICS, e si presenta quando le memoria libera per lee applicazioni è meno di 200MB.
Sotto questo limite, non si riesce più a installare nulla e compare il messaggio di memoria quasi piena, è assurdo.
Non so se anche con GB si presentava, perché ai tempi avevo meno app installate e quindi più spazio libero.
ps: voi quanto spazio avete libero per le app?
Lo vede in Impostazioni --> Applicazioni, in basso a destra
Oppure in Impostazioni --> Memoria --> Spazio dispositivo --> Disponibile