A 750W power supply does not draw 750 watts of power from the wall, thus it doesn't mean you need a 750VA UPS.
You could use this guide to help estimate what a single machine would need;
UPS Selector Sizing Applications
And you don't need a 2200VA APC UPS for your 2 workstations. I use one of those to power en entire telecom rack at my office. And they are nearly $2k.
With any UPS, you typically have to replace the batteries every 3-5 years. I'm sure your batteries have just reached the end of their useful life.
I'd say this would happily power both of your systems for 5-10 minutes...which provides plenty of time to shutdown in an outage;
APC Smart-UPS 1000VA LCD 120V
http://www.apc.com/products/resource...se_sku=smt1000
It's a $400 unit.