Would a fresh install fix the problem? Could installing 64 bit ubuntu or booting into a LiveCD help?

Perhaps it is certain Bios(es) and certain CPU's that the kernal has trouble with?
Is there a way to reinstall the kernel, or something along those lines?