As respostas lá são escritas para situações em que não há kernels porque os pacotes que os fornecem foram removidos.
Sua situação é semelhante, mas um pouco diferente. Parece que o que aconteceu no seu sistema é que não há kernels porque seus arquivos foram apagados manualmente (ou deletados por algum processo automatizado outro do que a desinstalação do pacote). Parece que, no que diz respeito ao gerenciador de pacotes, você ainda tem kernels instalados.
Para resolver isso, pode ser suficiente simplesmente para dizer ao gerenciador de pacotes para reinstalar o pacote do kernel.
Você executou este comando:
apt-get -y install linux-image-generic
Usando o mesmo procedimento (incluindo o comando apt-get update antes dele), tente substituir o comando apt-get -y install por este:
apt-get -y --purge --reinstall install linux-image-3.8.0-29-generic linux-image-extra-3.8.0-29-generic linux-image-generic
(O --purge flag é opcional, já que este problema não está relacionado aos arquivos de configuração do sistema. Mas isso não deve atrapalhar.)
Isso desinstalará os pacotes que não estão funcionando (devido a arquivos excluídos) e os reinstalará, garantindo que todos os seus arquivos sejam copiados dos arquivos do pacote. Ele não deve depender de nenhum arquivo de pacote presente, portanto, ele deve funcionar mesmo que alguns arquivos de pacote pareçam ter sido excluídos manualmente.
linux-image-generic é um metapacote; instalá-lo faz com que o kernel estável mais recente para o seu sistema seja instalado, porque linux-image-generic declara os pacotes fornecendo esse kernel como dependências. Estipular que linux-image-generic seja reinstalado "do zero" não necessariamente faz com que todas as suas dependências sejam reinstaladas, razão pela qual listei explicitamente suas dependências relevantes no comando acima.
Eu recebi os nomes deles ( linux-image-extra-3.8.0-29-generic e linux-image-extra-3.8.0-29-generic ) da saída que você incluiu na sua pergunta. Alguém que esteja enfrentando esse problema não necessariamente desejará estipular exatamente esses pacotes para instalação, mas deve ver quais pacotes linux-image-generic depende e explicitamente reinstalar pelo menos o pacote que está faltando arquivos.
Assim, a parte da saída que me levou a sugerir essa solução foi:
Setting up linux-image-3.8.0-29-generic (3.8.0-29.42) ...
Internal Error: Could not find image (/boot/vmlinuz-3.8.0-29-generic)
dpkg: error processing linux-image-3.8.0-29-generic (--configure):
É possível que isso não funcione. Isso pode acontecer se os pacotes forem quebrados de uma forma que impeça o gerenciador de pacotes de desinstalá-los . Se isso ou qualquer outro problema ocorrer, atualize sua pergunta com detalhes.
(Para as pessoas que não são o autor da esta questão - se isso acontecer e as informações aqui não permitirem resolvê-lo, publique uma nova pergunta com o maior número de detalhes possível ou adicione detalhes para sua pergunta se você já postou um sobre o problema.)