I have an Athlon II x4 620 overclocked to 3.25GHz. When my ambient temperature is 20C, prime95 (a program that puts 100% load on all 4 cores) load temperature is 55C. The Tcase max of this CPU is 72C. That means the temperature in which the CPU will start throttling should be over 100C. It should not have shut down either way though because if it went above the max temperature throttling, it would have throttled itself.
I am running the stock HSF with the stock thermal compound. There is something wrong here for you but a new cooler is not the solutions. Let's get some more details:
1. What is the case and case fan setup?
2. Is the HSF properly aligned and locked in place with thermal compound applied? Reseat it.
3. Is there any dust buildup? Remove it. Do not use a vacuum.
4. What are your ambient temperatures?
5. If you can, run CPU-z and HWmonitor and post screenshots of both.