Se você reinstalar o Ubuntu 16.04 como UEFI, ele deverá resolvê-lo.
Eu estava acostumado com a inicialização herdada, mas finalmente experimentei o UEFI com um laptop novo. Funciona bem, mas o que eu não percebi inicialmente, quando eu estava tentando instalar o Ubuntu a partir de um pendrive, é que eu tive que pressionar f12 na inicialização (para me oferecer o 'one-time boot menu') e então selecionar o stick sob as opções de UEFI.
Se eu não fizesse isso, bastava ler o stick como um boot legado e, se eu procedesse a instalá-lo da maneira usual, o Ubuntu e o bootloader grub seriam instalados no modo 'legado'.
Como o Ubuntu e o grub estão seguindo as regras do Legacy Boot, eles não têm 'permissão' para inicializar uma partição do Windows UEFI e, assim, você recebe o erro.
Se o Ubuntu estiver instalado no modo UEFI, o grub poderá inicializar uma partição UEFI do Windows sem problemas.
Seu menu de boot grub (além do Ubuntu 14.04 que eu instalei) provavelmente será parecido com isto: