Edite seu arquivo /etc/fstab e comente ou remova a entrada para /boot/efi ; isso deve acabar com a mensagem de erro. Agora você está inicializando o Ubuntu no modo BIOS, não no modo EFI, portanto, não precisa mais da partição /boot/efi . (Essa partição é a "partição de inicialização do FAT32" que você mencionou anteriormente, também conhecida como a partição de sistema EFI ou ESP).
Dito isso, minha suspeita é que você está inicializando o Windows no modo EFI. Em caso afirmativo, você provavelmente precisará usar o gerenciador de inicialização do seu firmware para selecionar o sistema operacional a ser inicializado. Isso pode ou não ser conveniente. Se você preferir usar outra coisa (GRUB Legacy, GRUB 2, rEFIt, rEFInd ou qualquer outra coisa), será necessário fazer com que a reinicialização da EFI volte a funcionar no Linux. Excluindo o ESP e recriando um novo, você também excluiu o carregador de inicialização do modo EFI para Linux. A correção que você seguiu foi a maneira mais difícil de fazê-lo; A maneira mais fácil era inicializar no modo EFI (usando o instalador do Ubuntu, por exemplo) e usar o programa efibootmgr para adicionar o carregador de boot Linux EFI (provavelmente o GRUB 2) de volta às opções da NVRAM. Você ainda pode fazer isso, mas terá que desinstalar o grub-pc e reinstalar o grub-efi. Isto implicará saltando através de um número de aros. Alternativamente, você poderia alternar para outra coisa, como o GRUB Legacy, o ELILO ou o carregador de stubs EFI do kernel (se você estiver usando um kernel 3.3.0 ou posterior). Consulte a minha página da Web nos carregadores de inicialização EFI para obter muito mais informações sobre essas opções. No geral, se você está feliz em selecionar seu sistema operacional do jeito que está fazendo agora, provavelmente é mais fácil manter esse método, pelo menos a curto prazo.