SInce you are familiar with linux, why dont you try booting a linux distro like knoppix from USB (
http://www.pendrivelinux.com/). If you can get it up an running, you can run a hard drive check. Most likely reasons for failure are usually power supply, or hard drive. Usually power supply is a complete failure, though. If you can boot linux, also run their memory checker.
No, even when i booted into Linus it was inconsistent, and now it runs fine. I did not touch the memory after swapping them out to no avail.