Se, come dici è random, prova a cercare nell'hw, non nel sistema.
memtest86+. Instsallalo da repository e fallo girare almeno un ciclo completo.
Test della cpu. In base alla tua disponibilità di ram, avvia con un live al minimo (tipo una knoppix cui dai l'opzione 2 all'avvio, così da fermarti alla console di root); fallo solo se hai parecchia ram, circa 1GB oppure dando al sistema una bella swap dove scrivere.
Scaricati i sorgenti del kernel da kernel.org (se il tuo pc non ha il collegamento via cavo e con knoppix devi faticare, salva l'archivio prima in una chiavetta o in un file system che poi sai aprire anche da knoppix).
Scompatta i sorgenti, dai un
make --defconfig
o qualcosa di simile per generare la configurazione di default. Poi compila il tutto con
make-kpkg kernel_image
Se ti dà un seg fault è la cpu.
GipPasso.