I just don't agree with throwing parts at a problem.
O2 sensors are the most needlessly changed parts on cars. Pretty sad when one considers how easily tested they are, at least for use on OBDI vehicles. That said, without going into detail about what the TCCS does when open loop, a dead sensor should not cause fuel economy to suffer to that extent unless there are other problems. I say should because it's possible but unlikely.
You can also check the sensor off the car using a propane torch. Look in my old SME section for the procedure. Kind of moot now though because you went and bought another. Since troubleshooting this symptom should have started by checking the loop anyway you're back to square one. You simply arrived there the most expensive way. Try it, let us know, and we'll go from there.
Keep in mind *accurate* fuel economy can be difficult to ascertain. Everything I'm telling you is predicated on your claim of 16 mpg. You didn't say how you arrived at that or even what your typical mileage is. It matters because say, if your mileage is higher the problem could be the O2 sensor alone. The point is we're trusting the figure you supplied to be accurate. If it's not we're pissin' in the wind...