Must surely be a hardware problem, as you have seen the same symptoms on different OSs.

I too have once seen this caused by a problem with the RAM - in this case it generated unusual BSODs under WinXP - something to do with a paging/memory error when I looked it up which was a big hint . Yes, those BSOD screens can be useful ...

As well as blowing the dust out of the case, I also took the precaution of cleaning the edge connectors on the RAM strip, as they looked slightly dirty. You can use any type of neat (or nearly neat) alcohol to this - in extremis you can even use something like Vodka, as it has no sugar content