I understand that the motherboard was just replaced. Apparently, the primary power cable, the 24 pin power cable is connected, but double check that the additional 4-pin power connector is also connected. This is a second power cable with a square 4-pin connector that plugs into a different spot on the motherboard. From a picture I saw online of your motherboard, this is probably on the top left of your motherboard. On some computers, this is partially blocked by the cpu cooling fan, so it can be easy to miss.
If that is connected, follow what cmiller5400 said. You will probably need a voltage testing power supply tester or another power supply to test if the power supply is bad. (I highly recommend getting a power supply tester that tests and displays actual voltages. I have personally seen a power supply that tested ok with a junky tester that did not test actual voltages fry a new motherboard so that it had the same problems as the old motherboard, but then the tech replaced the power supply and this did not solve the problem either, because now the new motherboard was fried. The problem was only figured out after the tech had fried 2 new motherboards.)
