Embaraçosamente, essa foi uma simples questão de instalar o grub-legacy e precisar instalar o grub2. Tendo dito isso, não sei por que o legado do grub se recusou a reconhecer novos kernels, mas instalar o grub2 resolveu o problema.
o grub-legacy substituiu o grub2 quando uma lista de aplicativos instalados foi copiada de um servidor anterior.