Sometimes the cat doesn't fail, but the backpresssure rises for a different reason. Sometimes the insides of the muffler fall apart. Do you drive where there is frequent cold weather and you have long warm up times?
Anyway, I say check fuel pressure, then exhaust backpressure.
Not all cats fail due to an engine running badly. Sometimes heat cycling and vibration can be bad enough to make it fail.