I see no need to waste money on another cooler. If the fan spins, the cooler works. Hunks of aluminum don't just stop conducting heat.
If the cured bond of the TIM is broken, you absolutely need to clean the mating surfaces and apply a fresh new layer of TIM. Then you need to make sure the cooler's mounting bracket is properly fastened. Contrary to what many want us to believe, OEM coolers today are more than adequate at keeping the CPUs they came with comfortably cooled within their normal operating range AS LONG AS it is properly mounted with a properly application of TIM, the case is doing its job of supplying a nice flow of cool air through the case, and you are not doing extreme overclocking.
If your temps are still way up there, then you need to look at your case cooling - still before worrying about the CPUs cooler. You typically want good front-to-back flow of air through the case. See what your case fan options are. You may be able to simply add another intake case fan in front, or an exhaust fan on the back.