Problema resolvido! Não tenho certeza do que realmente aconteceu, então vou postar todos os passos.
1) Reinstale o Ubuntu, certificando-se de designar que o bootloader deve ser instalado na partição EFI. Para mim, isso foi / dev / sda1. Anteriormente, eu tinha instalado o bootloader na mesma partição que o Ubuntu (sda2).
2) Siga este tutorial. Parece ser Sony Vaio específico, que é o que eu tenho. Acontece que a Sony às vezes usa um BIOS personalizado estranho que não funciona bem com o procedimento padrão de inicialização dupla.
3) update-grub e reboot
4) Viola! O Grub agora mostra o Ubuntu e o Windows no menu iniciar e eu posso inicializar na inicialização.