Yo uso dos cosillas para liberar espacio: localepurge y deborphan: el primero te elimina los locales que no configres como repdeterminados para guardar de documentaciones y demás (recomendable dejar el inglés por si algo no está en castellano, que es habitual).
El segundo te localiza los paquetes deb instalados cuyas dependencias inversas están vacías... o lo que es igual, librerías que se instalan al instalar un programa X, y que al emiminar X no suelen borrarse.
P.D. Localepurge en s primera ejecuión suele cargarse unos 500 megas, al menos a mi