The BIOS "Stay off on power loss" setting should not keep the system from booting. That setting tells the computer what to do when the power comes back on after a power failure - stay off or boot back up. It won't keep you from turning the computer back on at the switch, just keep it from booting back on it's own after a power failure. Pulling the battery would indeed reset the BIOS settings, but that is probably not your problem.
How old is the battery in your UPS? Most retail UPS batteries aren't good for more than 3 years. When the power failed, did the UPS kick in and provide power to allow your computer to continue running? If not, you're UPS battery may be dead. You can replace the batteries in most UPSs, but it's often easier just to buy a new one.
When you try to start the computer, does anything happen? Does the power light come on? Does the cooling fan start spinning? Will it work if you disconnect it from the UPS and plug it straight into the wall?
My initial guess is you've either got a bad power supply in the computer or a bad UPS. If it doesn't work when plugged straight into the wall, it's probably the power supply. This is an inexpensive fix for your local computer repair shop. If it works when plugged into the wall but not plugged into the UPS, your UPS is probably toast. You can get a new one at most electronics retailers. Don't spend less than $35 or $40 or you'll be buying a piece of junk.