Yeah it's a custom rig that a friend built for me. I figured that wasn't true. I've already paid the $50 diagnostic fee (which can be applied towards whatever fixing I needed), so it's kind of annoying to walk.
I might have to ask to talk to the owner of the store.
Although it doesn't hurt to clean the fans and replace the TIM, you can check to see if you are actually having temperature issues. You can run Prime95 to load the CPU and use Coretemp to monitor the temps. TJMAX is probably around 100c, but I would be worried if you are hitting the 90s on the stock cooler or 80s on a custom one at stock speeds and voltages. Intel CPUs are have great thermal throttling so check if the CPU is being downclocked under load. Ivy Bridge (3000 series) temps will be higher than Sandy Bridge (2000 series), but a reference point many custom coolers will keep temps in the low 60Cs under P95.
For heat issues, make sure your case and fans are clean. Compressed air (if using the cans, keep them upright) works. I use a shop-vac as a blower (run it a few seconds away from the computer to make sure the air stream is clean). I also hold the fan blades in place.
TIM/paste can lose performance over time and some types suffer from pump-out. It isn't too difficult to remove the cooler, clean the top of the CPU and bottom of the heatsink with isopropyl alcohol (90%+ if you can), and reapply new TIM. With the Intel stock cooler with push-pins you will need access to the back of the motherboard to remove it. Same with some customer coolers.
If it is the stock Intel cooler:
You could probably find a brand new on on Ebay or CL for under $20 as many don't bother to use it (I have 2 unused). Or you could pick up an aftermarket cooler for around $20-$30 (sale/rebate) + tax and shipping that would provide much better performance. This one is probably the most popular at that price point:
http://www.newegg.com/Product/Produc...82E16835103065
Or you could go up to something like this which is basically top-end air:
http://www.newegg.com/Product/Produc...82E16835608024
Or look into All-In-One (AIO) water from around $60-$120:
http://www.newegg.com/Water-Liquid-C...ategory/ID-575
Finally, if you already have a custom cooler, you almost certainly replace the fan with an appropriate 80, 92, 120, or 140mm fan for $5 to $20.