Was it a real cold day? Did they do it on the dyno?

On my cars, I ussually change the oil right before hand. I run them hard and get them very hot.. try to be the first one there in the morning. You can simply fail if the cat isn't up to temp.
Is it running rich? Maybe the temp sensor is out of range- you can measure it and compare with spec.
Is the new cat a factory cat or some cheapo aftermarket?

M