The Ubuntu disk actually has Memtest 86 on it, ironically enough. Just use that to test the system's memory. It does sound like a memory issue, though. I had a box like that once.

Also, I agree...