So you screwed the new O2 in the exhaust pipe and plugged it into the harness on the firewall?

Did you buy a 'Universal' O2 sensor and splice it into the old wiring harness?

The universal one's are (can be) garbage, and fail for any ONE of these reasons:
1) Incorrect sensor for your car
2) Poorly spliced into the old wiring harness
3) Soldered into the old wiring harness
4) Incorrectly wired into the old wiring harness
5) Correctly butt-spliced with crimp connectors into the old wiring harness with insulating sleeves, but old harness connnector and/or wire is 20 yrs old and corroded and toast. Anything blocking the air from the connector to the sensor through the harness will keep it from working properly.
6) Pinched or skinned wire insulation, even slightly squished insulation will keep it from working properly.
7) Slow response from new sensor even though everything above was done correctly, but your too much of a cheapskate to buy an OEM fit O2 sensor.
8) The old sensor was fine but you didn't fix the vacuum leaks yet
9) All of the above

If so then go and buy one made for your car and PLUG it in. Sometimes saving money is done by spending it in the first place, like getting all new vacuum hoses and not just the one's you can see are bad.