Welcome to the world of modern computing - they eat energy like crazy, and in 110 V installations this is becoming a problem. It seems that in the second when the Mac is starting up all the fans and HDs, it needs all the amps that your socket can supply. Have you loaded it up with lots of HDs? Sometimes you can stagger the start of the HDs to spread the load a bit, but you probably need to move the Mac to an outlet that is on a different, larger fuse.
UPSes can help hide this problem, but the problem is that you need a BIG UPS to power that Mac Pro. Check the exact specs of the Mac Pro in your manual, but I think you need something like a 1100 VA UPS.