When my old power thirsty 550 .25um athlon overloaded my power supply (high overclocking) I'd get random reboots. Usually when I spun up a 2nd hard drive, or a CD rom or something.
When I put in my new PSU it stopped.
The actually fact of having an AMD certified sticker is very unimportant, my PowerWin 450watt doesn't (though PowerWin's 300watt does lol).
What matters is that you supply enough current on the +3.3V and +5V combined rails for the processor you want to use.
If you look at AMD's site they will give you a list of power supplies that will meet the current requirements for different speed grades.
If you find a brand A power supply that supplies X amps that is AMD certified and a brand B power supply that suppleis X amps that is NOT, they will both work equally well.
(This is assuming that both are well made, and actually put out X amps, not just have a sticker that says they do).
Since the average person won't be able to figure out how much current a power supply needs, AMD's reco list is an easy way to figure out if it supplies enough.
Follow that?