Well the CX 600 is not the best power supply in the world but it's not by any means a bad one either. It should be plenty of power for your listed system.
Has that ever happened before?
Even though the CX 600 is a quality unit it still could be a bad unit as even the very highest quality models have a bad unit slip through sometimes. So the question is do you have a bad power supply or a bad motherboard. Asus boards show that error when they think the power supply is not sufficient for your components.
Any way to try a different power supply? If I had to guess I would say it's most likely a bad power supply but there is a small chance it could be the board too.
No it has never happened before. I was playing sims 3 on high graphics when it happened. But I have played more graphically intense and possibly more power consuming games like Skyrim, Borderlands 2, etc. on high graphics. I have had the computer for about 3 weeks.