Ajudaria a saber qual versão do Grub você está usando. Grub1 vs Grub2 na verdade tem um grande número de diferenças (muitas vezes irritantes). O principal aqui é se você tem um arquivo /boot/grub/menu.lst (grub1) ou /boot/grub/grub.cfg (grub2).
Estes são os arquivos que controlam o que você vê no menu do Grub quando liga o computador pela primeira vez. Em condições normais, você não deve editá-las manualmente, pois os scripts de atualização lidam com isso para você, mas como você disse, isso não é possível nesta situação. Então, faça backup desses arquivos e edite-os manualmente para as versões de kernel apropriadas. Se apenas consertar um desses arquivos não for suficiente (já que, como você disse, o / boot / grub está quase vazio), eu instalaria a mesma versão do Ubuntu em outra máquina ou drive, então copiei o conteúdo. Espero que as configurações sejam semelhantes o suficiente para que você possa inicializar, mas não há garantia de que isso funcionará.
Faça o que fizer, faça o backup de todos os arquivos antes de editá-los ou substituí-los!