O bom reinício de toda a máquina ajudou, mas ainda não tenho ideia do problema.
Atualização: pode haver uma causa - quando o VB detecta uma versão mais recente, você fica preocupado com a instalação de versões mais recentes. No entanto, se você executar a máquina virtual, e esta caixa de diálogo não aparecer (e deve), então o VBox pode acabar com algum estado estranho - a máquina virtual não é realmente iniciada, mas você não pode iniciá-la. Diálogo não é mostrado, então você não tem idéia do que aconteceu.
Por enquanto, é o meu melhor palpite.
Estou marcando isso como resolvido (porque resolveu o problema para mim), mas se você tiver uma ideia, adicione sua resposta também - obrigado.