Comment 5 for bug 6550

First off, grub doesn't uncompress the kernel. The kernel image is wrapped in a bz program that uncompressed it into memory.

For things to be failing like this, the problem has to be in this decompression stage (the bz wrapper). Either grub isn't jumping to the correct place in this loaded program, isn't loading it to the right place, the bz wrapper is broken (highly doubtful), or the hardware has a memory related issue.

Have you run memtest to make sure everything there is ok? Try reseating your memory modules. Have you tried resetting your BIOS to factory defaults? This could also cause problems (badly mapped shadow memory, etc.).