Eu experimentei o mesmo problema.
Atualizada do Ubuntu 13.04 para o 13.10 e o Virtual Box não pôde mais iniciar nenhuma máquina virtual.
Ele exibiu a "caixa de diálogo 0%" como na foto por alguns minutos, depois mudou para uma barra de progresso "20%", e depois disso nada aconteceu.
O uso da CPU para o VirtualBox é de 2% ou menos.
As últimas duas linhas do VBox.log são:
00:00:16.340506 Audio: Trying driver 'pulse'.
00:00:16.350789 Pulse: Audio input/output stopped!
Portanto, desativei a placa de som na configuração da máquina virtual e agora o VirtualBox iniciará as máquinas virtuais novamente.
Ótimo!