I'd first look at the FAN on the CPU cooler and see if its spinning.
Redoing paste is fine, but I wouldn't think that would suddenly be an issue.
If your current cooler is STOCK I'd get a new one simply to reduce noise. Without knowing what you have to ensure compatibility, here's two examples:
1) Cooler Master Hyper 212 EVO ($25+ USD)
2) Noctua NH-U12S ($50?+ USD).
You can check pricing at pcpartpicker.
Differences:
STOCK-> hear in idle, noisy under load, not suited to overclock usually
CM..EVO-> slightly hear in idle, acceptable under load, some overclock
Noctua U12S-> inaudible in idle, barely audible full load, best overclock of the three.
*I'm comparing based on systems with no other noisy components, and assuming you setup a proper fan control configuration using motherboard software utility. The Noctua for example can idle at 300RPM and can't be heard from six inches away.