Have you replaced anything else? (anything that would cause software glitches?) You haven't made any changes in BIOS, etc? (I'm just asking because most people get a new heatsink to overclock...) It seem to me that this is more likely to be a software issue. Hardware tends to either work or not work -- less of this in-between stuff.
Post full system specs too. including age of system.