John, I have done some further investigating and found I may be incorrect with my previous answer. NUT is supposed to do what you want.
A-Power goes out.
B-Battery gets low.
C-NUT issues a shutdown.
D-During shutdown, NUT issues a command to the UPS to turn itself off after the shutdown.
E-Mains come back on.
F-After the batteries have charged themselves back up, the UPS turns the power back on to the server.
G-The server reboots.
Common reasons why it may not have worked:
1-Your motherboard/bios may not configured properly. Are you sure you have it set to "power up after power outage" and NOT "return to previous state"?
2-The UPS doesn't support it. eg. it uses a *dumb* cable or does not know how to kill itself.
3-Some UPS's get themselves into a "race" condition. If this is the case then you need to do some extra configuration.
4-NUT is not configured/working properly and you may have found a bug.
Because of the large numbers of UPS's out there, it is impossible to configure NUT for them all. The devs used the most common configuration and in may not be correct for your UPS.
Please go here
http://www.networkupstools.org and read the FAQ and Documentation. About 2/3 the way down the FAQ page it talks about your probems.
If you think it is NUT or the way it is configured, please raise a bug in the bug tracer.