What is your PSU's brand and model? Crappy PSUs may not have enough hold-up time while under load to keep going until the UPS kicks in - relays can take close to 8ms to close and some PSUs don't hold even that long even though the ATX spec states 16ms as the minimum.
As Nuke said, there is also the possibility of a PSU with an APFC circuit which has a particular distaste for stepped approximation, in which case no amount of swapping one stepped approximation UPS for another will ever solve your problem. In that case, you can either buy a new $60 PSU that will work fine with your $100 UPS or buy a "pure sine wave" UPS for which your only option below $200 is Cyberpower.