Entre na sua BIOS (geralmente Delete, F1 ou F12 na inicialização) e habilite o VT-x.
Esta deve ser uma configuração em algum lugar no seu BIOS. Dependendo do tipo de computador, você pode estar em configurações de hardware, configurações avançadas ou algo semelhante. Olhe em volta para isso.
Também pode ser chamado de virtualização de CPU.
EDIT: Veja meu comentário abaixo. A virtualização aninhada não é suportada pelo VirtualBox. Em outras palavras, você não pode executar o AVD dentro de um sistema operacional convidado. O primeiro convidado (o Ubuntu, neste caso) usará o VT-x no host, mas não poderá fornecer o VT-x ao convidado aninhado (AVD). A solução aqui é dual-boot e rodar o Ubuntu como o SO host.