Just had the same problem with mine, randomly turning off, especially when from a cold start. Looks like this is very common with mac pros... Do you get a relay "click" from the power supply and an instant shutdown? If so the power supply is most likely and something is causing the circuit breaker to trip. When I took the PSU apart the solder joints were shockingly poor, brittle and cracked, it should never have left the Delta factory like it, amazing it lasted as long as it did. I ended up re-flowing 90% of the solder on the top circuit board - DO NOT attempt repairing the psu unless you know what you are doing!
Try the following:
The manual -
http://www.scribd.com/doc/17539946/Mac-Pro-Early-2008
iStat is good for keeping a check on how many amps the psu is able to supply or if anything is overheating
Check for kernel panics
De-dust and re-seat any video/pci cards & ram
Reset the SMC
Boot from a spare drive etc if you can - my HD got ruined, disk utility said it was toast, Disk Warrior fixed it

Check the power connectors etc on the logic board are seated ok
Check the error codes on the logic board between the ram risers - a pencil reaches in there nicely - all in the manual above. Even if the psu lights are green and the trickle power is amber (for ok) it doesn't mean the psu is ok...
Start the mac from cold - a cool environment will show up any bad solder joints easier. If it trips out try warming up the psu with a hairdryer, aim it through the holes at the top back and only at the psu - nicely warm it up don't cook it. Try it again, if it boots up bad solder is likely in the psu. Then it's time to get the psu looked at and fixed (check the electrolytic capacitors etc too), or shell out for a way over priced replacement

Good luck & hope this helps