No final, consertei isso baixando e instalando manualmente os cabeçalhos da versão do kernel que uname -r
me deu. Eu usei estas instruções do ubuntuhandbook.org .
Então eu reiniciei e escolhi opções avançadas para mudar para o kernel correto (de lowlatency para generic).
Por fim, consegui instalar e usar a caixa virtual corretamente.