I feel ya! Mine failed for the second time yesterday! I too had the EGR replaced and the EGR tubed cleaned. Despite running and idling marvelously, it did better but still barely failed the HC low and high speed tests!
I couldn't see the numbers on our chart well enough, but at ths point, I would venture that the cat is in need of replacement...not unlikely due to the mileage you've logged (on the original?). I'm staring down the same issue.
I noticed the words DISCONNECTED on a couple of places on the sheet...I know CA is pretty harsh on visual inspection. Is the smog pump disabled or are there critical smog components missing in the engine compartment?