Battery voltage does not accurately reflect capacity. Only a load test will determine battery health. Much like a body of water can be silted up and shallow, a battery will accumulate internal damage that prevents it from providing sufficient power while under load.
The new battery may not have arrived fully charged. If it has been installed for a little while and given a chance to charge fully you should measure a voltage greater than 12.6. (disconnect battery and let it rest a few minutes before testing). If the voltage is below 12.6 you might have gotten a dud. Do a load test on the UPS to see how long it can power something like a 100 watt incandescent bulb.