Curiosamente, nenhuma das respostas publicadas funcionou para mim. No entanto, por qualquer motivo, depois de instalar um monte de atualizações no Windows 10 (para a última versão, 1607) tudo se resolveu ...
A única coisa importante que notei foi que o 'Gerenciador de Inicialização do Windows' foi mais uma vez mostrado na ordem de inicialização (anteriormente ausente, por razões desconhecidas). Não tenho certeza por que atualizar o Windows teria tido tal efeito - executar o reparo de inicialização do Windows via USB não ajudou em nada (ele sairia com um erro indicando que o reparo de inicialização não é possível).
Depois disso, consegui instalar o Ubuntu sem nenhum problema. Queria saber exatamente o que aconteceu e por quê, mas parece que essa terá que ser uma daquelas situações de acidentes felizes.