Update on the situation.
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?