A couple of possibilities come to mind. Yes replace the battery and verify that it is the correct size. They can give a decent voltage but be close to dead. Clean and check the battery contacts. When the crown is pulled out to set time does it seem loose?
If the above does not work then check with Timex for a replacement movement. If those are not available then it's time for a new watch.