A execução de sudo update-grub
gerará um novo arquivo de configuração para o GRUB, mas você ainda precisará (re) instalá-lo em seu disco rígido. Em um sistema não-EFI, onde o GRUB está instalado no MBR do primeiro disco rígido, você pode fazer isso com
sudo grub-install /dev/sda
Se você estiver em um sistema EFI ou se seu GRUB estiver instalado em outro lugar, será necessário atualizar sua pergunta e nos fornecer mais informações antes de podermos ajudar.