I would still look at that PSU as being the problem, maybe not only with the startup issue but also with instability in your overclocking endeavor. 400W is the minmum Nvidia recommends for that GPU. While they tend to inflate that, still, if the PSU is not a cheap one to begin with and is aging it could have become inadequate.
It would be interesting to see if you returned your CPU back to stock frequencies and lowered the vcore to about 1.35 if the startup problem would disappear. It could be just on the margin of having enough power from the PSU to be able to start up. Overclocking the CPU might be pushing it to the edge and lowering the clocks and voltages might push it back from the edge a little. Or, better yet, if you were to temporarily swap out the video card with one that draws less power.