Olá Gonzalo_VC,
Um recurso nativo do sistema para fazer essa correção é pelo próprio Gerenciador de Pacotes Synaptic, tudo por ambiente gráfico e simples, que v. encontra no menu normal.
Marque os kernels que v. quer remover para remoção completa, incluindo as imagens correspondentes e o resto ele faz tudo sozinho, ao final apresentando o menu do grub já atualizado.
No campo "Filtro Rápido" preencha com 2.6.3 e ele irá listar todos os linux-headers e linux-image instalados.
O que tiver instalado ao lado esquerdo aparece com uma marca, um quadrado, na cor verde.
Click com o mouse sobre a linha para marcá-la, depois com o botão direito do mouse click em "Marcar para Remoção Completa" e depois, acima, click em Aplicar.
É bastante simples de ser feito.
Obviamente só remova os kernels antigos se v. tiver certeza absoluta que o kernel atual está funcionando à contento.
Informações adicionais, consulte:
http://ubuntuforum-br.org/index.php/topic,83443.0.html[]'s