Não sei se sua CPU do PAE está sendo tratada como uma CPU não-PAGE. No entanto, tivemos a mesma mensagem de erro, Esse kernel não suporta uma CPU não-PAE , e isso funcionou para nós:
O kernel não suporta um convidado KVM de instalação de CPU não-PAE no Ubuntu 13.10 - Corrigir
...
Basicamente, você só precisa garantir que o pacote linux-image-generic (ou seja, um kernel que suporta CPUs não-PAE) seja instalado configurando o sinalizador addpkg da seguinte forma: --addpkg=linux-image-generic