I agree it sounds like the cat could be getting old,but check the cap and rotor, be sure the oil is new, and be sure the car is already good and warm before the test, 20+minutes on the highway right before the test is ideal. Do not turn the car off while you wait. setting the timing back 2 or three degrees should help with NOx. The shop may heve a thermometer to check the cat with. If your car has air injection to the cat, be sure it is working. I think with a little luck, and a good waqrm up cycle, you might pass this time. I have seen some pretty new cars fail just because they were tested from a cold start.