Desde que fiz essa pergunta, atualizei minha máquina para o Windows 7 de 64 bits com uma nova instalação. Além disso, atualizei o VirtualBox no Windows e no Linux para a versão 3.1.2. Agora sou capaz de inicializar o Linux no VirtualBox hospedado no Windows 7 e inicializar o Windows 7 como convidado em um host Linux na mesma máquina. Muito legal!
O Windows 7 resolveu esse problema para mim. Ele detectou a mudança do controlador de armazenamento em massa, configurou-o e começou a instalar os outros drivers do VirtualBox, todos na primeira inicialização do VirtualBox. Quando eu reinicio no Windows nativamente, não há problemas para inicializar como costumava fazer.
Para resumir, a solução foi atualizada para o Windows 7.