I just found out the cats were changed about 3 yrs ago.

Would faulty O2 sensors cause these same symptoms? I've been getting O2 codes off and on for a while now. Would that be a good place to start?