I have a feeling you have a serious PSU problem. So before doing anything else, I'd be replacing my PSU. Look at the recommended list, there are lots of options there.
Next, I'd have a look at the CPU HSF. Did you replace the fan on that? If yes, then it probably was a bad idea. I'm sure they put a 8000 rpm 80mm fan on top for a good reason. (LMAO at the "quiet at 5000 rpm" bit

)
Check your HSF mounting. Is it properly mounted? What's the thermal interface material (TIM)? Was it a thermal pad? If it's anything other than Arctic Silver, I strongly suggest you clean the surfaces and reapply TIM, preferably Arctic Silver 5.
Check these out first. I think after the PSU change, you may want to keep your mobo. If the TIM application doesn't solve your heat problems, I suggest you get a whole new CPU HSF (state your budget, and we'll suggest something) Bigger case fans on fan ducts is usually a bad idea.
Clean out the insides of your case (reroute your cables for max airflow) Then check if your case fans do the job or not.
These are all good suggestions to do BEFORE you consider changing over to an Athlon64. You may just get to keep your dollars or, if you still decide to upgrade, prevent you from overheating your new processor.