And the answer was - PSU.

 

Which is funny.  So my old OCZ600MXSP is good enough for an ASUS M5A78LM_PLUS but apparently, the Gigabyte AB350M-D3H doesn't really like it. Got an EVGA 500B instead - works like a charm. Go figure.