i don't know why you replaced the O2. catalyst efficiency codes get set because the rear O2 is switching too fast (on a graph, upstream o2 will produce a waveform that switches constantly, downstream should have a [relatively] flat line.) bad o2's tend to quit generating the proper voltage- they don't start working extra hard because they're bad (and by 'working' i mean generating voltage based on the presence of oxygen). typically either they become unresponsive or the heating element gets burned up.
make sure you don't have any exhaust or vacuum leaks. anything that can cause the presence of extra oxygen in the exhaust could concievably set that code.
as far as CA vs non-CA cats: no idea. but unless california does really weird inspections, they probably just stick a mirror under the car and make sure the exhaust looks factory and the cat(s) are present. as long as you haven't welded in a universal cat or something, i doubt any red flags are gonna go off with a non-CA drop-in replacement.
someone mentioned ECM's. that would be my only concern- that your ECM calibration is specifically for CA smog parts. i doubt a higher flowing cat would cause any issues, but it may be worth mentioning, especially since someone did say they'd had experience with maximas being overly sensitive to catalyst eff codes (i30 = maxima).