just to let you know, I have cali emmisions gen 4 also and went with installing some aftermarket headers. Even after replacing the a/f sensor with toyota brand I still get the 1130 and 1135 codes. Sooo, hopefully it will fix your problem you are having, but do not get your hopes up.

But then again, my problem might be different from yours, so good luck.
and as far as the o2 cel eliminator, Im assuming its for the catalytic code you are getting? they are very easy to install, just make sure you know what wire to splice into.