Hi fmashockie,
We know for sure that the UPS thinks that one of the relays is faulty - but there may or may not actually be a relay problem. Based on my experience with a different APC product, the UPS may be detecting AVR relay weld faults by measuring its input and output voltages. The buck/boost operation changes the ratio of the AVR transformer to buck/boost the output voltage relative to the input voltage. The UPS can't actually detect what the relays are doing directly, but it can look at the ratio between the measured input and output voltages. If that is not as expected, it might trip the fault - essentially assuming a relay is stuck in the wrong position. So if one of its voltage measurement circuits is faulty, it may incorrectly detect a fault.
However, you say that it outputs 120V with an input of 130V... that would suggest to me that its voltage measurements are OK, because it's doing the right thing under those conditions at least.
If you have replaced all the relays (and the old ones tested fine anyway) and it's still doing this, then I would suspect that one of the relay driver circuits is faulty.
Why would it only work at high input voltages and fail otherwise? That seems like an important clue as to which relay is failing. Based on that, I'd say the AVR trim relay is not working, so it's basically stuck in voltage trim mode. As soon as you drop the voltage to a point where it would usually switch out of trim mode, it tries to and fails, and trips the fault.
I guess you'd have to figure out which relay is the trim relay, find the drive circuitry for that relay, and troubleshoot it. I'd start by looking at it, in case anything is visually blown - and then compare its input signal (from the microcontroller or other circuitry) with its output to the relay coil, to see if it's working as it's supposed to. A schematic would help a lot with that, which may be available online somewhere.