Two Poweredge R510s reboot randomly within seconds of each other.

I have two PowerEdge R510's that have begun to reboot within seconds of each other.  I have two APC Smart UPS 3000va UPSs in place.  They are older and have just had the batteries replaced.  A call to APC determined that the new batteries must be calibrated in these older UPSs so I bought two 1000va UPSs.  Each server has redundant power supplies.  I put each server (both power supplies) on a single 1000va UPS with no other devices on the UPS... both UPSs run at about 30% power with the servers on them.

These servers began rebooting every 6 or so days about 3 weeks ago.  It has increased to every few hours at this time.  The log file seems to write after the server has rebooted so I am not sure if the machines are blue screening or not... I do know that they both reboot within 60 or so seconds of each other.

Any help with this issue would be helpful.

Mike