Então, /jpiserhard/, vinha igualmente acompanhando a sua busca de solução em paralelo lá no "Ubuntu forums" gringo, onde o tema evoluiu bem, assim, se permite, penso ser importante também referenciar aqui o caminho lá trilhado, vez que pode ser útil para outros usuários que venham a enfrentar idêntica questão, pois que, afinal, a finalidade de um Fórum é não apenas encontrar soluções para casos individuais, mas sim formar uma base de dados sólida que possa auxiliar vários casos similares presentes e futuros, vale dizer, o objetivo é não apenas o indivíduo, mas principalmente a comunidade de usuários.
The package linux-image-2.6.36-020636-generic needs to be reinstalled, but I can't
http://ubuntuforums.org/showthread.php?t=2246404
Peço desculpas por não ter postado ainda como fiz para resolver meu problema. Estou bem ocupado com faculdade e tudo o mais, consegui tirar um tempo ontem só para por o tópico como resolvido. Hoje não tenho aula então estou com umas 3 horas livres e vou postar agora como solucionamos o problema do meu Kernel.
Exatamente, eu postei meu problema lá no "ubuntu forums" gringo e teve uma discussão bem solida sobre o problema. Vou postar abaixo como eu fiz para resolver o problema:
Após varias tentativas de remoção do Kernel falharem, tentamos re instalar ele como o sistema pedia, mas também não conseguimos. Eis que surgiu um membro do fórum que apenas postou um código que removeria a "força" o kernel.
sudo dpkg --remove --force-remove-reinstreq linux-image-2.6.36-020636-generic
E foi esse codigo acima que removeu a Kernel do meu sistema, após isso ainda tinham alguns problemas que a Kernel deixou para trás, que foi resolvido com a atualização do GRUB
sudo update-grub
e também fizemos uma verificação de arquivos do sistema
sudo touch /forcefsck
E então é só reiniciar o computador.
Mais uma vez queria agradecer a todos que de alguma forma tentaram me ajudar.