O carregador de inicialização do Ubuntu, chamado Grub (que fornece as opções de seleção de inicialização), precisa ser reinstalado.
Já que você já tentou a ferramenta de reparo de inicialização, e não está funcionando, tente a outra opção como respondida por @ scott-severance aqui: link