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 that Ubuntu is not necessarily the best distro out there. It's quite bloated, but it is relatively easy to use. Fedora is equally bloated, and also easy to use. You could try going with that, but remember it is Red Hat based, while Ubuntu is Debian based. There are some major differences there.