Obrigado pelas suas respostas.
Após verificar os logs, não encontrei nada indicando que a máquina virtual encontrou um erro, o que é estranho. Eu pensei que talvez extrair a imagem do cd pudesse levar algum tempo e deixá-la por quase uma hora e nada aconteceu.
De qualquer forma, o problema está resolvido agora. Até agora a versão do Virtualbox instalada no meu sistema era 4.1. Parece que outros usuários passaram por dificuldades semelhantes. Eu forcei o Virtualbox a atualizar para a versão 4.3 (a versão mais recente do VB não estava na minha lista de repositórios). Kali agora está inicializando em tempo razoável e funcionando bem.