Seria interesante saber que ROM llevas para poder aconsejarte (supongo que alguna ICS)
Pero la memoria a la que se refiere ese mensaje no es la "masiva" o SD (donde copias las fotos y musica), sino la de aplicaciones, ubicada en la carpeta /datadata
Con la aplicacion DiskUsage (
https://play.google.com/store/apps/d...roid.diskusage) prueba a entrar a Espacio Root -> datadata y ahi podras ver el espacio libre que tienes y que aplicaciones te lo estan comiendo
Y una vez tengas ubicadas las apps que te consumen ese espacio, solo tendras que ir a Ajustes -> Aplicaciones y buscarla, entrar y darle a Borrar Datos
Una practica recomendada para evitar que se colapse innecesariamente es, a la hora de restaurar aplicaciones, hacer la mayoria sin datos (es decir, solo la apk) y solo las necesarias con datos, aparte de restaurar solo las que uses
En las actuales ROMs JB se ha solventado ese problema
PD: Consejo personal, rehuye de cualquier fix de datadata que veas. No son para nada recomendables