Make sure you are using the correct 4 pin connector. Your motherboard uses a 20 pin main power connector. Most power supplies come with a detachable 4 pin connector for use with a more modern 24 pin motherboard. This 4 pin is not the same as the ATX 12V 4 pin connector you are supposed to be using for the CPU. I only mention this in case you got them mixed up.
There should be a sticker on the side or bottom of the psu with a chart listing voltages and amps ex: 12v/30A, 5V/20A,etc. or in boxes such as 12v in one box and 30A in the box below, 5v in the box next to 12v, and 20A below it, etc.. (it may not be 30 or 20A I was just useing those as an example).The label should also list the manufacture or at least the brand of the PSU (some are better then others if there is a ul number [a backwards UR symbol with a number under it] this may lead to the actual OEM). This information is importent since not all PSU's are created equall. Infact many cheaper 500w PSU's actually only output around 200w. Since the psu is new it is suspect but might not necessarily be the cause. By the way why did you install a new PSU? If you still have the old one and it is working try it and see if it eliminates the problem, If you replaced the old PSU because it failed it may have taken other hardware with it. and as mailpup said the 4 pin P4 connector is not connected to the 20 pin main and should have 2 yellow and 2 black wires as well as it's owin clip for secureing it to the motherboard.