Minhas máquinas conseguiram inicializar normalmente após desabilitar a aceleração 3D no VirtualBox.
Configurações > Mostrar > Tela > Aceleração > Ativar aceleração 3D (desmarque)
Uma correção alternativa é bem-vinda porque eu estava usando o 3D Acceleration bem desde sempre, então eu não entendo por que ele tem que ser desativado, ou se é realmente o culpado. Como o recurso estava funcionando antes de 18.04, suspeito que seja um novo bug não relacionado a problemas anteriores.