Hmm. I'm fairly certain the keyboard fails to work when I haven't
pressed any keys yet (not even 'return' to select the kernel in
GRUB--it usually just picks the first one after 5 seconds). I can't
for the life of me think of what would make it occur only
occasionally, though.
My gut instinct is to declare, with a 98.625% confidence level, that
your keyboard/keyboard connector is flakey.
You may have missed the part where I said that I had this problem on two
different laptops. I was certain it was hardware as well on the first
laptop (a Dell Latitude), but then I got a brand new IBM Thinkpad X40,
and the same behavior occurred immediately out of the box. The Latitude
was nearly new as well.