Eu verifiquei os parâmetros de inicialização do kernel e (não sei por que, mas) nolapic foi definido. Depois de remover este parâmetro e reiniciar tudo estava bem.
Em detalhes: eu editei /etc/default/grub e removi nolapic na linha GRUB_CMDLINE_LINUX="..." e depois atualizei grub sudo update-grub e reiniciei.