Acabei de ter o mesmo problema. A única coisa que ajudou foi remover manualmente arquivos suficientes em / boot usando
cd /boot
rm initrd.img-3.2.0-24-generic-pae initrd.img-3.2.0-29-generic-pae
para
apt-get -f install
para poder completar normalmente. Então use
dpkg --list|grep linux-image
para identificar imagens linux e remover o suficiente das antiguidades com, por exemplo,
apt-get purge linux-image-3.2.0-24-generic-pae linux-image-3.2.0-29-generic-pae ...
Finalmente, pode haver algum espaço extra para recuperar com
apt-get autoclean
apt-get autoremove
(eu deduzi o acima de outras respostas - isso foi trabalhado para mim)
Eu acredito que eu vi que o Ubuntu agora tem algumas funcionalidades de "limpar velhos kernels", mas aparentemente ele não entrou aqui.