When you look at the heatsink, make sure that you pulled the tab off the pad.
Also, keep in mind that the stock AMD heatsinks with those thermal pads only make contact with about 10% of the CPU. The means all the heat that your CPU products has to be dispersed through a very small part of your heatsink. Try getting a higher end heatsink and fan with some thermal paste. Artic Silver is a trusted brand.
It's like runing a Chevy big block and cooling it with a house fan. Sure it will run for a while, but sooner or later it's gonna blow.
As far as your powersupply, how many watts is it? A good way to see if it's your PS is to boot up with only our hard drive and vid card. Don't connect any sound cards, NIC's or CD/DVD roms/burners. If it boots then you are correct, could very well be your PS. But I don't know how many watts you can push out of it.