If in fact that warning message appeared after an automatic shutdown, it means that your processor initiated the shutdown because it sensed an over temp [correctly or incorrectly as i have seen faulty P4 chips that would do this]. You should ensure that you have installed the processor correctly [including the correct cooling fan with the thermal interface material] and that your cooling fan is still working. As I stated before, I have had bad P4 which would shut down randomly with this problem and the fix was a CPU replacement.
You may be replacing your processor. But you can significantly drop the temperature of the processor by applying thermal grease between the surfaces of the processor heatsink-fan assembly and the top surface of your processor. Also, check if the heatsink snuggly fits on top of the processor. Be sure that your processor fan spins normally and can dissipate the heat of the heatsink effectively. Do also check the temperature reading by going to the bios setting then to “hardware monitor”, you should see the temperature reading of your motherboard and processor. If you want clearer procedure, visit http://clhidohardware.blogspot.com