Graças aos comentários do @Rod, que me apontaram na direção certa, consegui resolver esse problema. O que aconteceu foi que minha máquina tem 5+ anos e tem uma cópia antecipada da UEFI, que parece ignorar a ordem de inicialização da EFI. Em vez disso, ele insiste que o ESP deve estar em / dev / sda1 e em minha máquina estava em / dev / sda3 como resultado de inúmeras alterações nas configurações de disco.
Eu precisava excluir todas as partições no disco e excluir a própria partição GPT. Depois disso, criei um novo conjunto de partições com o ESP como a primeira partição, chegando em / dev / sda1. Finalmente eu reinstalei o Ubuntu 17.04, reiniciei e tudo deu certo.