I personally wouldn't touch that power supply with a 10 foot pole, and would bet money that it's the thing causing the shutdown. Without knowing your full system it's hard to make an accurate suggestion on the PSU you should use. Perhaps 500W would be enough, but I wouldn't trust that PSU to actually be able to output 500W. Also, the 70% efficiency that it claims is atrocious. For a rough number, you can go to
http://images10.newegg.com/BizIntell/tool/psucalc/index.html and input what you know about your computer. I would suggest going with a little more power than it offers.
Also, the best power supplies have a single rail. It's pretty cheap and easy to build a power supply that is basically several low-wattage power supplies in one, which has several 12V rails. You have to be careful with a power supply like that not to over-stress any of the individual rails, so even if you are below the stated max total power draw, you can be over-stressing one of the rails. I didn't see anything on the power supply that you got that would suggest that it is a single rail design, so that may have been your problem. You might want to read
http://www.tomshardware.com/reviews/low-cost-psu-pc-power-supply,2862.html.
It can be hard to tell a good power supply from a bad one, and a low price quickly catches the eye. Don't be fooled by cheap PSUs that are really only suitable for e-mail/internet browsing machines. It's easy to slap on a label that claims 500W, since so few people have the means to test the claim.
If you find a power supply you like better, you can post a link/picture here and I/other forum members can weigh in on the unit. I hope you find something that works.