Eu finalmente encontrei uma solução para o meu problema que não envolvia a exclusão da partição do Windows. Como outro apontado, o problema era que minha instalação do Windows era uma inicialização legada da BIOS, enquanto o Ubuntu agora estava usando o UEFI, que é incompatível.
A solução foi converter a instalação do Windows em UEFI. As únicas coisas necessárias eram o dvd de instalação do Windows (ou um pendrive UEFI inicializável) e um Ubuntu funcional.
Primeiro, converta a partição do Windows em GDP
sudo gdisk /dev/sdX
Command (? for help): w
em que sdX é a unidade do Windows.
Em seguida, inicialize o disco de instalação do Windows e, em um prompt de comando, execute as etapas detalhadas em este link a partir da etapa 7. Isso substituirá a partição de inicialização do BIOS existente por uma partição de inicialização UEFI.
Após essas etapas, você pode executar
sudo update-grub
para atualizar seu menu de inicialização.