Pesquisando no Google este relatório de erros do RHEL . Agora, eu sei muito pouco sobre o SELinux, mas eu me lembro de ter visto um relabelamento do SELinux após atualizar minha distribuição OS, meus problemas com o SELinux aconteceram casualmente após uma atualização do kernel e o relatório de erro sugeriu tentar um autorelabel forçado criando um arquivo vazio no sistema diretório raiz chamado .autorelabel
.
Então, criei esse arquivo, reiniciei meu computador, esperei a conclusão do autorelabel e tentei executar uma VM novamente. Minhas VMs agora iniciam normalmente e o problema é corrigido.