Yo tengo ese mismo problema desde hace mucho tiempo. Haz una cosa, mira en root explorer cuanto espacio libre tienes en data. Te digo lo que tengo yo, que hoy me ha salido el cartelito... y comparamos.
Yo lo que hago es pasar el sd maid cuando me lo dice, siempre me libera unos megas que me van bien.