aptitude autoclean
aptitude clean

y reiniciar para comenzar en un nuevo kernel por defecto

También puede ayudar

du --apparent-size

du -x / | sort -n

Archivos no necesarios que podemos borrar. Atención: Estos comandos no se podrán deshacer, algunos puede que los necesitéis o queráis conservar . Os recomendamos que vayáis paso por paso y aseguraos que realmente queréis borrarlos.

rm /var/log/*.gz

Fuentes:
http://www.debian-administration.org/article/627/What_to_do_when_the_root_partition_is_full