El primer paso es conseguir algo de espacio en la partición "/boot" porque sin eso es imposible hacer nada.
Así que ve a /boot y elimina algunos ficheros "initrd", ya que son los más grandes. Con unos cuantos será suficiente.
Después de eso es bueno asegurarse de que no hay ninguna instalación parcial pendiente de terminar:
apt-get -f install
Ahora es buena idea purgar todos los kernels excepto el que se está ejecutando:
dpkg -l 'linux-*' | sed '/^ii/!d;/'"$(uname -r | sed "s/\(.*\)-\([^0-9]\+\)/\1/")"'/d;s/^[^ ]* [^ ]* \([^ ]*\).*/\1/;/[0-9]/!d' | xargs sudo apt-get -y purge
Para evitar que en el futuro se llene la partición, es buena idea instalar y ejecutar periódicamente: purge-old-kernels. La instalación y un ejemplo de uso son:
# installation
apt-get install bikeshed
# keep three old kernels:
purge-old-kernels --keep 3
# if you want to put that in the crontab use that command
purge-old-kernels --keep 3 -qy
Si eres usuario de Grub no olvides ejecutar:
update-grub2
Personalmente tengo una pesadilla con ese problema y con Ubuntu, especialmente con la versión 12.04 que está instalada en un montón de servidores que gestiono. He repetido el proceso anterior muchas veces y al final decidí documentarlo porque siempre tengo que ir a Google y encontrar los pasos adecuados para resolver ese problema.