Você precisa reinstalar o Ubuntu, mas sem mudar para o modo Legado no BIOS. O Ubuntu suporta o EFI perfeitamente. Tenho certeza que seu problema é que a versão EFI do Windows 8 foi instalada, enquanto você instalou a versão BIOS / Legacy do Ubuntu.
Tente inicializar na parte legada do Windows quando estiver EFI não funcionará. Você também pode tentar isso, caso não queira reinstalar o Ubuntu. Inicie o Ubuntu e abra uma janela de terminal. Então corra
sudo update-grub
Isso pode funcionar, mas acho que o primeiro método funcionará muito melhor.