Replaced both upstream O2 sensors today (Hands are all cut up too!), used cleaner like you said... before the swap, and also added a can of B12 to my fuel.
No check-engine lights so far after about 60 mile combined city/highway.
I will report more results after more milage.
Car has 103K miles, had original O2s, and P0430 codes..
thanks Brian!