Não esqueceu do sudo update-grub?
Esqueci não, o menu encontra-se desse jeito mas as versões 2.6.31-15-generic e 2.6.31-14-generic estão desinstaladas!
Ubuntu, Linux 2.6.31-16-generic
Ubuntu, Linux 2.6.31-16-generic (recovery mode)
Ubuntu, Linux 2.6.31-15-generic
Ubuntu, Linux 2.6.31-15-generic (recovery mode)
Ubuntu, Linux 2.6.31-14-generic
Ubuntu, Linux 2.6.31-14-generic (recovery mode)
Memory test (memtest86+)
Memory test (memtest86+, serial console 115200)
Microsoft Windows XP Professional (on /dev/sda1)
No Synaptic tem 2 citações do kernel : linux-headers e linux-image; removeu as duas?
Tenta pelo Terminal :
sudo apt-get remove linux-headers-2.6.31-14-generic linux-image-2.6.31-14-generic linux-headers-2.6.31-15-generic linux-image-2.6.31-15-generic
o código que você enviou retornou o seguinte:
george@george-laptop:~$ sudo apt-get remove linux-headers-2.6.31-14-generic linux-image-2.6.31-14-generic linux-headers-2.6.31-15-generic linux-image-2.6.31-15-generic
[sudo] password for george:
Lendo listas de pacotes... Pronto
Construindo árvore de dependências
Lendo informação de estado... Pronto
O pacote linux-headers-2.6.31-14-generic não está instalado, então não será removido
O pacote linux-image-2.6.31-14-generic não está instalado, então não será removido
O pacote linux-headers-2.6.31-15-generic não está instalado, então não será removido
O pacote linux-image-2.6.31-15-generic não está instalado, então não será removido
0 pacotes atualizados, 0 pacotes novos instalados, 0 a serem removidos e 3 não atualizados.