If you still have it, you might try taking the faulty encoder apart and cleaning it, and perhaps bending the internal contact arms so they press more firmly against the conductive disk. That actually works most of the time.
Or, you might post a link to the replacement you used. Perhaps someone will know how to find the inverse of that one.
You need to be careful that you get the right replacement. It isn't just the number of detents that may be different, which as you say doesn't really matter. But some encoders have the same number of pulses per revolution as detents per revolution. They go through a complete cycle of both switches between detents, and both switches are always open at a detent. The other kind has half as many pulses as detents per revolution. At each detent, both switches may be open, or both may be closed. They go through a half-cycle between detents.
If the software expects the first type, but you install the second type, you will have to turn through two detents to get one tick recognized. In the opposite case, you'll get two ticks per detent. Better to get the type your software is expecting. It looks like you got that part right, or you would have noticed even more strange behavior.