x86_64 = AMD64
No link do askubuntu o cara basicamente renomeia a pasta .VirtualBox (questão de segurança, depois o certo era voltar como estava antes) e desinstala e instala de novo o virtualbox. Na outra solução, 2ª, ele instala os headers do kernel, sem eles você não consegue compilar um módulo para o kernel, que é o que o virtualbox faz toda vez que é instalado ou atualizado. Um módulo seria na verdade um driver, mas em linux o mais correto é usar o termo módulo.
Mas é melhor baixar do site mesmo, se não me engano ele adiciona um repositório junto, para manter atualizado o virtualbox.