I doubt that the Bosch +4's would cause an O2 sensor problem on their own. Instead of replacing the O2 right away, try removing it from the exhaust piping, heat the housing that goes into the pipe until it glows orange, and keep it that hot for atleast 3 minutes. Let it cool, then spray it down with a non-chlorinated brake cleaner, doing your best to get the brake cleaner in and out of the openings. Repeat the heating and brake cleaner steps twice, the final time not using any brake cleaner. Reset the code, and see if it comes back.

A large majority of the time, when O2 sensor codes occur, ESPECIALLY slow response codes, it is the result of contamination from dirty fuel. This heating and brake cleaner cleaning often clean the O2 sensor out very well. About a year ago, I had my light come on reporting the same thing. I did what I prescribed, and the O2 sensor light didn't come on for about 10 months. After that, the cleaning no longer worked, but considering the sensor was about 4 years old, I wasn't complaining.