A exclusão da assinatura do disco resolveu o problema. Isso pode ser feito com o comando
dd if=/dev/zero of=/dev/sdb bs=1 count=4 seek=440 conv=notrunc
em um shell linux com direitos de root.
Antecedentes:
A partir do Windows 2000, a Microsoft grava um valor de 4 bytes - a assinatura do disco - no MBR de cada disco, para que ele possa identificar cada disco. Quando dois discos têm os mesmos problemas de identificador. O comando acima mencionado substitui essa assinatura por zeros que solicita ao Windows atribuir novos valores exclusivos.
Note que antes de sobrescrever a assinatura do disco, eu também tentei substituir o bootloader (bytes 0-439 no MBR) por zeros. Por si só, isso não ajudou a resolver meu problema.
EDIT: Esta solução resolveu o problema para apenas uma inicialização. Ao tentar inicializar uma segunda vez, os mesmos problemas reapareceram. Sobrescrevendo novamente a assinatura do disco, consegui inicializar, mas novamente apenas por uma vez.
A julgar pelo histórico fornecido acima, parece que o Windows escolhe uma assinatura de disco inadequada para que o problema reapareça ...
EDIT 2: Parece que ao inicializar no modo UEFI, o Windows 7 64bit não consegue lidar corretamente com partições estendidas em discos com MBR. O bug é explicado aqui:
Aparentemente, uma partição estendida é erroneamente reconhecida como uma partição UEFI. Esses dois hotfixes devem resolver o problema, mas eles já devem estar integrados à mídia de instalação.