[jcp123]

Long shot, but if it uses a wideband O2 sensor to monitor the cats, that can affect fuel economy, it gives more precise information to the computer. If it detects a bad cat, programming will dictate that the proper correction will always be to miniseries emissions, that is priority over fuel economy or any other consideration. I say it's a long shot because widebands are rare even now, and I doubt anyone was using them on a C-segment car in '04, but food for thought.

As for the cat itself, if it's an exhaust manifold-mounted front cat, those are notorious for short life, they are exposed to the hottest exhaust gases.