Hmm, that PSU seems to be a pretty hefty unit, and the RX 580 doesn't take much more power than the old 560Ti. Am I correct in assuming you have the settings the same in Overwatch as you had before?
My only concern with the PSU is that it's got 3 separate 12V rails, was orginally available in 2012 (older design), and, for a Gold efficiency unit, only has a 3 year warranty. Still, at over 900W available on the 12V rails combined, this shouldn't be a problem unless something's gone wrong with it over the years.
I've got to confess, clean driver install, and what appears to be far more PSU capacity than you'd need, I'm a bit stumped. If you have (or can borrow) a known good PSU, I'd try it out, just in case, but otherwise, I'm a bit baffled.