Como mencionado comentário
Eu apaguei a partição em que o Ubuntu foi instalado, refiz o particionamento, reinstalado o Ubuntu. Desta vez, em vez de escolher a opção recomendada para "instalar lado a lado com o windows", eu escolhi a terceira opção para fazer a partição eu mesmo.
Escolha
/dev/sda
para o grub-install. A instalação foi perfeita. Eu inicializado para windows e linux algumas vezes sem dificuldade.