Substituting a different psu is a great step - a "broken" psu causes so many strange symptoms its almost the first thing one should do lol.
Some other unlikely splutions:
If you are using a UPS, plug the psu directly into the wall for the time being.
Check for a heat issue - while I doubt this is the problem, the "slowing" of the system makes me ask this. Use CPUID Hardware Monitor for temps and let us know.
If you have another 4pin fan, you might try that on your cooler. You say that the fan starts and stops repeatedly, dunno whether this is the cause or an effect (most likely).
I assume you have set memory voltage and timings by hand at least once. If not, do so now. Use max memory voltage (I believe for your board its 1.65V).
You haven't mentioned clearing CMOS and restoring default values. When you clear CMOS, use all techniques lol . . . pull plug on psu, pull battery, press the case "power on" button several times, then wait 10 minutes. Restore defaults, save, reboot, ensure memory timings and voltage are set correctly, reboot.