gawkowsk :
It seems like the PowerShute's calibration is not sufficient in case of battery replacement.
I doubt it is a calibration issue in my case since the UPS starts beeping the low-battery alarm within seconds from switching to battery power, meaning battery voltage is dropping close to the UPS' minimum operating voltage as soon as load is applied. No amount of calibration is going to magically change the UPS's under-voltage lock-out and low-battery alarm thresholds. Once battery voltage starts collapsing (around 1.8V per cell for lead-acid), the battery is pretty much empty... this is not something you can calibrate your way around of.
When my cheap replacement batteries were fresh, it took 2-3 minutes for the low-battery alarm to go off. On the original batteries, it only started after ~10 minutes for the few times I had to dare stretch my luck that far. That was my first clue about how my new batteries were nowhere near the same performance class as the originals - but I already suspected that much from past shopping for a battery to put in my BK650.
The last time I had a power outage, it took me about three minutes to put my computer in hibernation and the UPS shut down from under-voltage lock-out just as I was about to press the UPS' button to turn it off. That's where my 3-4 minutes run-time came from; not PowerChute's estimation.