I had a similar problem. Took me weeks and a fair amount of money to figure it out, having replaced power supply and mainboard. I guess the takeaway here is never assume anything.
The computer is used in an air conditioned room, not overclocked, and has a zillion fans in the case, so I assumed overheating was not the problem until I booted to the BIOS and monitored the temperature. Watched it go up to over 90 C. This photo tells it all.
This was not obvious from a casual look at the APU. After cleaning, the temp went down to 56 C and stayed there.