Você precisa reiniciar com um CD do Linux (por exemplo, CD de instalação da Debian), em vez de entrar no modo de recuperação e montar sua partição raiz do Linux (e /boot se estiver em uma partição separada). Após esse lançamento grub-install como root no shell de recuperação (o shell rodando no sistema que você tem no seu HD).