Eu decidi reconstruir o kernel usando make-dpkg como mencionado no wiki do Ubuntu.
sudo make-kpkg buildpackage --initrd kernel-image kernel-headers
Eu gerou a imagem do kernel com:
sudo make bzImage
Se bem me lembro, em um PC, isso resultará em vimlinuz para: /usr/src/[your_linux_source_tree]/arch/x86/build
Os cabeçalhos que usei foram baixados de kernel.ubuntu.com/~kernel-ppa/mainline/
Por fim, fiz o update-initramfs, truque update-grub .
O ecrã do Grub não aparece? Aqui está a resposta