How did you apply it? Did you spread it yourself?
Best way to do it, is to put a pea sized glob right in the center, then place the heatsink down on the cpu. The pressure will evenly spread the paste, and you can wipe off any residual that comes out of the sides (if any)
Also, as far as thermal paste goes, I highly suggest Arctic Silver (
http://www.newegg.com/Product/Product.aspx?Item=N82E16835100008) for example (They have a lot of different kinds)
If that still doesn't work, boot up your system and keep an eye on the heatsink. Make sure your fan is running, and make sure you have adequate airflow.
If you're still having issues, try buying a new heatsink.
Finally, and worst case scenario, your chip may be going bad. Depending on how long you've had it, I'd suggest attempting to RMA it for a replacement.
Edit:: One other thing you could try doing - You say this problem started when you installed a new hard drive.... Make sure you get the proper chipset drivers for your mobo. This could cause conflicts and could possibly cause the temp issues you're experiencing.