The message (in your heading) suggests a problem with a memory module.
But changing the CMOS battery could have reset the BIOS to defaults so start by opening the BIOS screens and checking stuff (usually, hit the Del key as the machine powers up and follow on-screen instructions).
I read the manual for the Dell Dimension 4700 on how to properly reset the CMOS. I did what the manual said, but still getting the same error.
I have also read that it could be a RAM problem. Before installing the power supply I tested the RAM with the old power supply, and everything worked properly. With 4GB of RAM installed, dxdiag showed 3.3 GB of useable RAM.
I know that it is running Windows XP, but I don't know if any of the service packs have been installed on it.
After testing the RAM with the old power supply, I installed the new one. This is when I got the error message the first time. I tried to use the old power supply, and still got the same error message again.
This makes me think that I fried something... Is there a way I can test and see what is failing?