I am expanding my comments into an answer because I think some aspects of the specific problem are either being overlooked, or used to draw the wrong conclusions.
At this point, the question of whether to refactor is premature (even though it will probably be answered by a specific form of 'yes').
The central issue here is that (as noted in some answers) the comments you quote strongly indicate that the code has race conditions or other concurrency/synchronization problems, such as discussed here. These are particularly difficult problems, for several reasons. Firstly, as you have found, seemingly unrelated changes can trigger the problem (other bugs can also have this effect, but concurrency errors almost always do.) Secondly, they are very hard to diagnose: the bug often manifests itself in a place that is distant in time or code from the cause, and anything you do to diagnose it may cause it to go away (Heisenbugs). Thirdly, concurrency bugs are very hard to find in testing. Partly, that is because of the combinatorial explosion: it is bad enough for sequential code, but adding the possible interleavings of concurrent execution blows it up to the point where the sequential problem becomes insignificant in comparison. In addition, even a good test case may only trigger the problem occasionally - Nancy Leveson calculated that one of the lethal bugs in the Therac 25 occurred in 1 of about 350 runs, but if you do not know what the bug is, or even that there is one, you do not know how many repetitions make an effective test. In addition, only automated testing is feasible at this scale, and it is possible that the test driver imposes subtle timing constraints such that it will never actually trigger the bug (Heisenbugs again).
There are some tools for concurrency testing in some environments, such as Helgrind for code using POSIX pthreads, but we do not know the specifics here. Testing should be supplemented with static analysis (or is that the other way round?), if there are suitable tools for your environment.
To add to the difficulty, compilers (and even the processors, at runtime) are often free to reorganize the code in ways that sometimes make reasoning about its thread-safety very counter-intuitive (perhaps the best-known case is the double-checked lock idiom, though some environments (Java, C++...) have been modified to ameliorate it.)
This code may have one simple problem that is causing all the symptoms, but it is more likely that you have a systemic problem that could bring your plans to add new features to a halt. I hope I have convinced you that you might have a serious problem on your hands, possibly even an existential threat to your product, and the first thing to do is to find out what is happening. If this does reveal concurrency problems, I strongly advise you to fix them first, before you even ask the question of whether you should do more general refactoring, and before you try to add more features.