Yes... the sudden shutdown of your PC due to a power failure has the POSSIBILITY to adversely affect your PC. At best, you could lose important data depending on what your hard drives happen to be doing at the time of the power outage. At worst, you could lose components due to the sudden loss and return of power to the system, especially if the power outage delivers a voltage spike to your computer.
Most of the time, your computer will handle to sudden drop of power just fine... but the possibility definately exists that the computer could be damaged or the operating system corrupted during the power event.
The more critical question here is: why isn't your UPS keeping your computer up and running when the power goes down?
You say you installed a new battery? Do you mean that you put a new battery in an old UPS... or did you purchase a brand-new UPS?
If the UPS is brand-new, most of them require you to connect the battery to the internal wiring when you take it out of the box. Make sure your battery is connected.
It the UPS is old and you put a new battery in it, perhaps there is something wrong with the switching circuit that is supposed to toggle to the battery in times of power outages. If that's the case, you'll have to replace the UPS.
One other thing to look at, and please don't take this as an insult to your intelligence! I just want to cover all the bases possible to be thorough. On most UPS type devices, only a certain set of the plugs actually have battery backup... the others are surge protection only. For example, on an APC Back-UPS 550 ES there are 8 plugs, but only 4 of those are battery backup outlets. Check to make sure you haven't plugged your computer into a surge-protection only outlet. They should be clearly marked on the unit.
Another thing that could be happening is that you have an overdraw on the UPS. I've seen this happen when someone buys the cheapest UPS they can find, say a 280-watt model, and then uses that to backup a 750-watt computer plus a large wide-screen monitor and several other peripherals. The poor UPS just doesn't stand a chance against that kind of draw and fails quickly.
If you have a UPS that includes management software (like the PowerChute software that comes with most APC products), install that software and connect to your battery. You should be able to run self-tests on the unit to see if there are problems the software can detect.
I know there was a lot of information there... hopefully it will help you track down the cause of your UPS issue so you can protect your computer against power outages. Good luck!