Ik had een soortgelijk probleem. Niets hielp.
Op mijn PC zitten 2 harde schijven er er staan diverse OS op, XP en versies van 8.04 tot en met 10.4. Slordig, maar historisch gegroeid.
De grub startte steeds met 9.10. Update kernels tot 10.4, eerste versie waren zichtbaar, de nieuwe niet...
Toen heb ik gewoon het systeem zichzelf op laten starten op 9.10, de startupmanager met synaptic binnen gehaald, de opstartvolgorde aangepast en mijn systeem opnieuw opgestart. De grub lijst vertoonde nu wel alle kernels enz. en de laatste nieuwe 10.4...24 was geselecteerd, ergens op regel 7 of zoiets. Die startte dus gewoon op. Dus voor mij is het probleem opgelost.
Waarom, daar snap ik niks van, maar ja, ik snap wel meer niet