I wouldn't trust the baking thing except as an absolute last resort. And if it's anything like the Xbox 360 baking 'solution' it will probably last all of a week.
The simplest thing to try would be reseating the video card. You said you just replaced it, so that sounds like a good place to start. Reapply some fresh thermal paste, and personally I leave the tin enclosure off my video card after reading a recommendation here a long time ago: I was able to confirm that the GPU runs far cooler if you remove it.
And hopefully you've eliminated the basic software possibilities like trying a different driver set or even reinstalling Windows, just because it's far easier to cope with software issues than hardware.
I have to concur with the 'last time I saw that the video card was going bad' sentiment. I wouldn't chalk it up to buying refurbished or whatever, just buying from Ztronics since there's probably a reason they only have one week warranties or whatever.