Trying to understand CPU Heating!

Good day,

I have a PC (new) that is restarting (shutting down) because of CPU overheating. (This is how I analyzed the problem by looking at PC Health Status and other applications - I'm getting 60+ degrees, and when opening games it gets even higher).

Anyway, I did what I usually do, I replaced the CPU Fan and Cooler, and I even replaced the thermal paste on the base of the CPU Fan and Cooler.
It didn't work, it's the same!:confused

I just want to understand, is it a CPU or Mainboard problem? How is this? Isn't the heat related to the fan and cooler? I mean the CPU should always heat up as part of its normal operation, and the fan and cooler should cool it off, right?
Should I use very expensive CPU Fan and Cooler? Should I suspect the CPU itself?

 

It would help us to answer if we knew what type of machine and some specifications of it.
I have 3 machines (all Small Form Factor) that always seem to run hot, but they don't get fried while being run 24/7.

 

I am running two high end PCs 24\7 on heavy graphics and have some frightening temps, Over 100c on the GPUs (not constant) and 70C on the CPUs without any shutdown.
As Hrlow requested if you give us a few more details we will try to help.

 

Thank you all,

I hope you can help me to sort this out..

Here are the specifications of the PC:

CPU: Intel Pentium 3.4GHz/2MB/800Mhz FSB
Mainboard: MSI P31-Neo V2
Ram: Kingston 2GB DDR2 800MHz
HDD: WD 320GB 7200RPM/8MB
VGA: NVIDIA GeForce 9400 GT 1GB DDR2

Actually the power supply is the only flaw, it is the generic power supply that came with the case. They write 450W on it but it is not right, it is not more than 200W, but can this be the problem?

Thank you all in advance...

 

Thank you Halo,
The case model? Do you mean the form factor? It is P4 ATX Minitower
The cables are tidy and tied to the sides of the case..
There are only a CPU Fan and a side fan (2 fans)
I think there's a space for an extra back fan (under the power supply)
The PC isn't at my reach now so I will post back the full temp results as soon as I get to it...