Unless you know differently one cat wont have just failed, the lambdas should give you the information you need. Are you sure you dont have a faulty lambda or something else putting the emissions up.

How hard did the garage try to get it to pass? There are some tricks that can be used to get a car to pass, my tester will usually have a go if a car is close or was it way off? How long did the garage let the car warm up for before they tested it, a decent run down the local bypass in 3rd gear can often help secure a pass on a marginal car.

Steve