Veo que pasaste por alto mi anterior mensaje. Vuelvo a insistir por si acaso esta vez me lees.
El mensaje "no hay espacio de almacenamiento disponible" que da al intentar instalar una aplicación ocurre cuando intenta escribir el fichero y no puede, por lo que supone que es debido a que no hay espacio en disco, pero a veces es por que hay un fichero .odex para la aplicación que intentas instalar y no coincide con el fichero .apk nuevo. Por esta razón te deja instalar unas aplicaciones y otras no.
Busca esos ficheros .odex y eliminalos (creo que TitaniumBackup permite tambien borrarlos, pero no lo tengo seguro). Creo que están en /data/app (tampoco estoy seguro).