When it reboots randomly, are you getting any error messages or blue screens, or is it just a total black out and restart?
Also, you replaced the power supply? When you did, did you replace the power cord as well? If the power cord has a short in it, this can easily happen, or if there is some bad wiring comming to the computer. Have you also tried running the computer from a different outlet, possibly a different room or building just to see?
Do you have any extra peripherals (PCI acapters), video cards, etc, that you could run the computer without, in order to make sure it isn't one of them causing the problem? It wouldn't be a bad idea to test running it with nothing connected that isn't necessary. If you have onboard video, try running through that, without the video card (assuming you have an add-on video card), and without anything else connected. Just so long as it will run.
If you check all of that, and still rebooting, then my guess would be yes - the motherboard. There could be one little minute piece in the motherboard such as a compressor to go bad, and then you're best off just replacing it. Besides, for a 2400XP (assuming it's an Athlon XP) processor, you can get a new board cheap enough.