As a friend always told me, "The life of electronics is in the smoke."
The plan of using the other power supply is how I would proceed too. I would get a surge protected outlet (or even on an UPS if that is available) to plug into though which should reduce your risks of be short two power supplies.
The place where I buy power supplies, if that is all you need, is called 3B Tech (3btech.net). I have found their prices to be the best and shipping is free and reasonably fast (3-4 business days to Oklahoma).
If you have to rebuild the machine the questions will be: what are you looking for (aside from good linux compatibilty), how fast do you need it, and how much do you want to spend. If you've got a 7-10 days or so to be selective and can use some of the components from the old machine (HD, RAM, DVD/CD and any PCI cards you may use) and if you are happy with onboard GPUs then I would get on NewEgg's mailing list. I just built a machine case and all for ~$220 (AMD triple core 2.9GHz processor, 6Gb RAM, 750Gb SATA HD, ATI HD 4550 graphics card (had HD 4350 onboard), etc. All of this came from taking about 10 days to watch for special pricing. The power supply was from 3B Tech though.
The mobo is made by Gigabyte and has worked well with VL 6 series up to SOHO b3. I've loaded light, standard, and KDE classic and had no issues. I've also used a few live CDs (Parted Magic and Ultimate Boot CD) and had no detection issues (64 bit and 32 bit).