Refaça a instalação, dessa vez desconectado da internet para que o instalador não tente baixar atualizações enquanto instala
Depois de instalar o sistema e estar tudo funcionando, atualize
Não creio que esta sugestão funcione (e nem sequer consigo imaginar o que podem ter a ver atualizações descarregadas mas não instaladas com a falha de instalação do Grub).
O pacote 'grub-efi-amd64-signed' implica instalação em modo UEFI (correto para o modelo) e para tal a ESP (EFI System Partition) é necessária. Isto significa que se selecionamos o particionamento manual temos que criar uma partição FAT32 de cerca de 512MB no início da drive que tem a prioridade no arranque - no caso de o sistema ter mais do que uma a ESP e a partição principal do Ubuntu podem estar em drives diferentes - e depois selecioná-la como EFI durante a instalação, junto com a partição root (/). A partição swap já não é necessária. É ainda possível criar uma partição /home separada mas para a maior parte dos utilizadores iniciados tal não é necessário. Estes são os requisitos básicos de uma instalação em modo UEFI.
Ainda há que considerar o tipo de particionamento que deve ser GPT. Note-se que o Ubuntu não obriga a isto mas no caso de querermos um dual-boot com Windows, sabendo que este sim exige GPT para UEFI e MBR para BIOS, então faz todo o sentido usar o particionamento moderno que ademais não tem o limite de 4 partições primárias que MBR tem (em GPT deixa de fazer sentido falar-se de primárias, extendidas e lógicas, há apenas partições).
Para simplificar nada melhor que escolher a opção "apagar... instalar". Assim o instalador encarrega-se de tudo.
A minha sugestão foi pelo motivo dele descrever "
Erro muito chato, já tentei instalar de todas as formas, inclusive formatando o HD por total e nada. " e ainda assim não funcionou. Dessa forma, como você mesmo disse se ele estivesse usando MBR o software de instalação correria normal, legacy, onde não é necessário o EFI System Partition. Ou se estiver usando GPT, com o UEFI ativo no setup da placa-mãe, faria instalação EFI.
Observe o que o usuário descreveu na íntegra. Releia.
Se pesquisar verá que muitos usuários já tiveram o mesmo problema, ou outros por de alguma forma acabar por não baixar corretamente pacotes de atualização na instalação onde a atualização parcial de pacotes é feita e estando de forma incompleta, acaba obtendo esse erro. Após correr uma instalação sem conexão esses usuários não obtiveram o erro. Funcionou pra muita gente...
Outro motivo para o problema seria ele estar, como você sugeriu, usando instalação avançada em uma MBR criando a partição EFI para GPT, ou estar tentando utilizar uma instalação legacy com o setup da placa-mãe (Bios/UEFI) setada em modo UEFI only. Descartei essa possibilidade. Creio que não é apenas isso, pelo que ele disse.
Enfim... mas valeu pela colaboração!
Abraço