when it "overheats" does it shutdown?
IF it is not turning off then its not overheating.. it's something else then or you have some faulty board or CPU..
one question did you use the thermal paste the stock heat sink came with or did you add other stuff?
Another thing is IF you replaced the CPU paste did you do it correctly (no air bubbles, how did you apply it as it matters, etc.), also, what about did you install the CPU cooler then take it off then put it back on? IF you did put it on then remove it you NEED to reapply the cpu paste or it will cause issues. Just for reference this is what I always use
https://www.newegg.com/Product/Product.aspx?item=N82E16835426020 (gelid gc-extreme) and it works great. I though never use the spreader.. I just put a pea sized ( well smaller then a pea but a round ball of it) in the middle of the CPU and put the cooler on top of that. I have tried spreading thermal paste and such and never got good results that way as you always add a few air gaps between the CPU and the heat sink. Then then acts like a blanket (the air gaps).. other pastes I have used in the past were the artic silver 5 or something like that but I found that I had to reapply the junk about once a year as the stuff did not last.. (clean it up first then reapply.. don't add new to old stuff).
Edit: what is showing the over 100C temps? as some programs don't report correctly. and are you stock settings or Overclocking that thing to death