Com relação a instalação também usei o Debian 8 amd64 que tem suporte a UEFI também mas deu no mesmo.
Essa questão de atualizar a Bios/Uefi acho que tem um software da Samsung que faz isso no Windows 8, mas eu já apaguei ele, tem como fazer isso direto no setup?
Essa atualização depende muito da fabricante. Lá no Setup da Bios, não há opção para atualizar? Pelo menos no meu Asus, bastou eu baixar um arquivo do site, passar para um pen drive, reiniciar o notebook, entrar na Bios e procurar essa opção para atualizar. E também tem como atualizar por um programa do windows (que eu desinstalei!).
Você tentou usar o Boot Repair após a instalação do ubuntu ou debian 8? Você precisa de um pen drive ou live cd/dvd para isso, você dá boot no seu notebook pelo Live, instala esse Boot Repair, e roda ele para recuperar o boot do seu notebook.
Se não tiver jeito, use o "UEFI and CMS" mesmo.
Seria interessante você reportar como bug esse problema em relação ao UEFI, lá no debian. E se o problema relacionado ao desligamento continuar, reportá-lo também.