When you opened the laptop to install the new HDD on it, did you see any signs of cummulated dust on the fans, or on the laptop in general? a can of compressed air would be the best choice here.. Of course, this is if the problem is heat related, which to me it sound like it.
Download this program: Speccy - System Information - Free Download
And post a screenshot with the summary
that'll give us a hint about the temps.