Had a similar situation with my son's computer. For Christmas he received a new graphics card and power supply. The first time there was a problem all it took was unplugging the PSU connector to the motherboard. Worked fine, for a couple of days. Second time around, I popped out the pins from the connector and cleaned them with rubbing alcohol, as well as the pins on the MoBo. There was some resin flux residue left inside the female pins. Haven't had a problem since.

Worth a try anyways.