Eu entendo que o recurso de inicialização segura do Windows 8.1 complica a vida. Eu tive um problema semelhante em que eu só tenho Ubuntu, não o Windows. No entanto, acredito que a solução que encontrei sugerida em vários sites se aplicaria em ambos os casos, assumindo que a abordagem no post anterior não ocorreu.
Quando você estiver no Ubuntu (eu entendo que você pode entrar com alguma dificuldade) instale o "boot-repair" da seguinte forma: Openl Terminal (ctrl + alt + t) e digite os três seguintes comandos
sudo add-apt-repository ppa:yannubuntu/boot-repair
sudo apt-get update
sudo apt-get install boot-repair
Abra o reparo da inicialização do seu painel e selecione "Reparo recomendado". Daí em diante eu simplesmente fiz como me foi dito. No reinício, o Grub fez o seu trabalho.
Fonte: Numerosos, entre eles este: link