A ver, tal vez no me he explicado bien... Da igual el espacio que te diga que hay libre gracias al a2sd, yo he llegado a tener 900 mb libres y me salía el mensaje. Esto se debe a que aunque tengas ese espacio libre, la memoria interna del teléfono tiene poco espacio, y si esto ocurre, no te deja instalar ninguna app más.
Aunque tengas el a2sd activado, las apps siguen ocupando parte de espacio en la memoria interna, incluso algunas (creo que las que son del sistema) la caché también.
Si miras la primera imagen que pongo a continuación, verás que me quedan 983 Mb libres, pero sólo 52 en la memoria interna. Hay un par de aplicaciones que tengo quitadas porque ocupan muuucho en "Datos" y me dejan la memoria interna rondando los 20 Mb. o menos, y es eso lo que hace que te salga el mensaje.
En cuanto a lo del Titanium Backup te muestro otra imagen de como veo lo que ocupan para hacerme una idea de cual me puede estar dejando seco la memoria interna.
