I have a box running Debian on a 2 disk software RAID 1 + LVM2 setup. A couple of days ago a kernel security update was installed, bringing it to 2.6.26-17lenny2. Since then GRUB has problems booting properly.
Initial boot throws up "Error 13: Invalid or unsupported executable" and stops.
And here things go weird: the menu list contains a manual entry to an installation on another disk which is no longer there. Launching that entry results in a "disk doesn't exist" error as expected. But after that retrying the real entry now launches the kernel perfectly...
Similarly: using the GRUB shell to edit the root stanza to point to a non-existing disk, attempting to boot, then restoring it to the original entry makes the kernel boot.
Something in there is making GRUB change its mind on where to look for the kernel. The reason I suspect the softRAID is that the menu list displayed on boot does not match the one in /boot/grub.
I found one possibly related Debian bug (526525) that hints at an AMD64 specific problem, so for those with a similar setup, watch out...