You could try going into the BIOS at boot, usually by pressing F12 or Delete. There will be a CPU temperature in there somewhere, just watch that for a while and see how high it is. Depending on what brand and model of CPU you have, temperatures will vary, but if it is higher than 60 degrees, something isn't right.
As alexoiu said, try getting some new thermal paste and reapplying that, as well as this, maybe gaffer tape some of the cables out of the way of the air flow of the case.
Make sure nothing is blocking the CPU fan and obviously, before even going into your PC case, earth yourself. (I like to touch my PC case or Power Supply at the start and before i touch components)