O GRUB precisa residir na frente de todas as partições no dispositivo, portanto, você deve executar
sudo grub-install /dev/sda
considerando que o uso de / dev / sda3 o instalaria apenas na terceira partição. Veja o guia Recuperando o Ubuntu após a instalação do Windows a que você se referiu:
A partir daqui, encontre apenas o nome da unidade, ignore o número da partição , isto é, para partições rotuladas como "root", "data2", "fat", "home" e "swap" é tudo ainda apenas sda . Isso se deve ao fato de o GRUB estar instalado no MBR da unidade e não em uma partição.