Could be an overheating issue?
Try open the side of the case and blow a fan directly into the CPU area and see if the random restarts stop happening.
You did not mention the size of your power supply unit or the speed + make of your CPU.
Ever since I bought this new computer I've been having computer self-restarting issues. At first I thought it was the incompatibilities due to the video driver that came with the built-in video adapter on the motherboard. So I installed a nVidia AGP video card w/ the latest driver from their website which I thought that had soloved the problem, but thats not the case. I know its some kind of hardware problem but I just don't know exactly how to fix it or where to start to look. Everything looks OK in Device Manager and I have XP service pack 2 installed also. Computer restarts the most when I exit from a computer game (happens randomly on different games). And sometimes it just restarts randomly during any windows application. I have absoultely everything updated from Windows Update website and I run all type of virsu/adware/spyware scans so I don't think its any software related. Also because this has been happening since the day right after I installed a fresh copy of xp pro with nothing on it. So must be hardware.. Anyway, if anyone has any advise would be much appreciated..

Chowhound
Comic Vine
GameFAQs
GameSpot
Giant Bomb
TechRepublic