The sub O2 sensor is the one in the back - downstream of the cat. Only the CA vehicles have them.
It sometimes happens when you replace the primary O2 sensor - the computer compares the front and back and can tell if the sub sensor is reading too lean. The code could also indicate a burned out heater circuit. Either way, yes, unfortunately, you'll need a new one.
The aggravating thing is that sub sensor doesn't do anything of value - theoretically it is supposed to verify the cat is functioning, but it doesn't even have a code for a bad cat!
They're expensive at sparkplugs.com, - $97, and the NGKs are $93, not much help. Amazon has had really good prices on Densos lately - I got the Denso part num for the back sensor from sparkplugs and searched for "denso" plus the part number on amazon and they have it for $77 including shipping:
http://www.amazon.com/Denso-234-4154-Oxygen-Sensor/dp/B000C5SG8G/
Since it's the back sensor and it doesn't do anything useful for you, you might try to clean it. Probably won't work, but might be worth a try. They're tough to clean because they get a coating of very hard carbon over the sensor and that's what keeps it from reading the exhaust. First make sure the heater circuit is okay - if it isn't, cleaning won't do any good. Test the resistance of the two wires that are the same color - that's the heater circuit. Should be 4.5 - 6 ohms at 73 degrees F.
The only cleaning method I've ever read about that has some evidence of working is to heat the end of the sensor with a torch until it's very hot - nearly glowing, and then plunge the tip into water. The sudden shock is supposed to cause the carbon to flake off. You may have to do it a few times, and try flushing the tip with a forceful spray of water. Do this in a clean bucket or bowl so you can see if any tan flakes have washed out. Since alcohol is a wetting agent, I would add a 1/2 pint or so of 90% isopropyl alcohol to the water. Can get that at a drug store.
When you reattach the sensor, make sure there are no leaks as that would cause the sensor to read lean - giving you the code again. Another thing that can help is to clean the pins in the connector - a lean reading is a low voltage reading, and the same thing can happen if there's some corrosion in the connector.
As before, remove the EFI fuse for a couple minutes after changing the sensor to reset the computer. (I said 10 seconds in an earlier post but a number of people have reported that it took longer for the computer to reset.)
If you tried cleaning your old sensor, test it by driving until the motor reaches operating temp, and then in a high gear, floor the gas pedal for at least 5 seconds or so. That's what will trigger the code if it is reading too lean.
Good luck - let us know how you make out.