"Actually, since they have to pull so much stuff to get to the starter it is very possible they did not hook up a connector or sensor wire correctly and that threw a CEL. Getting a light right after major work generally points to an error made during the major work, not a new problem.

This is rather disturbing coming from a Lexus dealer. I would ask them what the code is and why do they think it is the cats?"



Do that get the error code or codes p0430(right or Bank2)p0420(left or Bank1).

 

Guys on OBD2 cars there are two sets of O2s the first ones are used to tune the car, the second set is AFTER the cats used to determine if the cats are working properly.
The eliminators are designed for the rear O2s when people use an Off road "H" or"test"pipe which does not have bungs for O2s.
I HIGHLY doubt both cats went bad at the same time.
Oh and the cats used on Toyotas do not break apart and come out when bad.
Fords can, yes.But Toyota uses a completely different type of converter.
I can hollow out a Ford cat in about 15 minutes, it took me almost 2 hours with air chisels,hammers and pry bars to do a Toyota one.