These really need to be properly tested, if you had a issue with the Cat, then it will generally set a cat code-P0420. The code you are getting is slow response, are you able to monitor the sensor via a scanner?

 

So what are some things that throw a "slow response" code. Could it be a faulty new O2 sensor? Been considering buying an inexpensive scanner.

 

Yes, for that code the sensor is probably the issue, but without monitoring it kinda hard to say. The other thing is, it maybe the wrong sensor...like wrong year,etc. I think I'd return it, and verify correct one.

 

Just write down the Denso part number located on the side of the sensor and confirm. They may have given you the wrong one, such as one for a ULEV engine. Also, you stated you replaced both sensors on the car. Did you put them in the correct places? If the connectors are the same and the wires reach it could easily be done.