The paste has nothing to do with your problem. Some people forget to put new past on when they pull a heatsink and you then can cook your CPU. So a power supply swap. That is your best bet for now given you have R&R'd everythng already. Can you swap the PSU from the puter you are on now and see what happens. It would have to be a 24 pin PSU as well.
Noli Nothis Permittere Te Terere!!
EVGA 680i, Dual EVGA 8800GT'S (650/950), 4 gigs OCZ DDR2 1066, Intel Q9450 at 3.8 Ghz, Koolance Water Cooled, Dual Plextor16x DL DVD+/-RW. Dual WD 250gb 16mb Cache Sata 3.0. 3DMark06 score = 19,168.