|List exactly the power supply make and model to be sure, but it should work fine.|
Remove and reseat the video card to make sure it is completely seated.
Do you have the 6pin PCIe connector properly connected?
Does your power supply have the 6pin PCIe connector or are you using the twin Molex to PCIe 6 pin adapter? If yes, do you have it connected to two Molex 4 pin connectors on DIFFERENT wire runs? Using two connectors from the same wire run does not allow sufficient amperage to reach the card since you are using the same wire redundantly which is just like using only one of the two connectors. Connecting to two different wire runs allows amperage to flow from two completely different wires and possibly two different 12Volt rails (on multi-rail power supplies) so sufficient power to reach the video card.
Did you see if you need to change any settings in your BIOS, especially if you are going from onboard graphics to a distinct video card?
You have to be a little bit crazy to keep you from going insane.