Yes this is an old post. Sorry for digging it up, but because I have the same issue and found something I consider report-worthy, I wanted to search for the same problem but didn't want to make a brand new thread.
I've noticed that if I let grub count down from 5 seconds to 2 seconds, I'm able to go ahead with my kernel selection. If I make my choice and press enter within one second or so, it comes up with this message. By extension, my suspicion is that if you allow your bootloader to count down from 30 seconds (if that's your timer), you should be fine to select your kernel at 27 seconds.
Also, this could be related to some people's reports that noapic or noioapic don't do anything for them.
I'm using the default 2.6.22-14-generic kernel from Ubuntu 7.10.
I don't know what the issue could be, but this might help someone be a little less frustrated.