If you are confident that the 02 circuits are OK, that there is no corrosion going on and the connections are secure, then it's not the 02 sensor that is causing the code. Instead, the engine is running lean.
Lean = too much air getting into the combustion chambers and/or not enough fuel. Common causes of too much air are vacuum leaks (i.e., disconnected or deteriorated hoses, PCV & EVAP system leaks, intake gasket leaks) and fuel delivery issues (i.e., clogged fuel filter, bad injector(s), faulty fuel pump).
A thorough examination of the engine bay for vacuum leaks is in order. And a great place to start regarding possible fuel issues is a new fuel filter (if not replaced in a while) and a fuel pressure check:
http://members.aol.com/racsan99x/Fue...ureTesting.doc