Tente instalar os pacotes linux-generic, linux-image-generic e linux-headers-generic. Esses meta-pacotes dependem do kernel e dos cabeçalhos mais recentes. O kernel emitido mais recentemente deve iniciar por padrão, e você pode verificar as opções adicionais do menu GRUB para outros kernels realmente instalados.