If the engine is really running too cold, then it is the thermostat. Your car will get bad mileage if it never warms up, because the engine requires more fuel to run when cold. Does the heater take a long time to warm up, and does the temp gage show low temp? My 2.8 A4's thermostat was open about 1/8" cold when I took it out.

$600 is a lot of money to change a $30 part, but maybe that's the going rate. Most people recommend changing the water pump, timing belt, and rollers at the same time because the labor is nearly the same.

I have a 2001 A6 with 85K miles on it. I've broken every almost every possible thing that is common on this car, including this problem.

To check it: Drive the car for 10 Minutes, the Oil temp gauge should be at the first mark (2nd mark is fully warm). (The Coolant should have warmed to the center of the gauge first, if it didn't you need the thermostat.)
Now drive at highway speeds, turn the heat on manual to full blower and high on both the driver and passenger side. If you see the coolant temp go down at all you need a thermostat.
While you are replacing it, do everything else that is in there: Water pump, timing belt and all tensioners and the belts. Absolutely replace all of the coolant with new coolant. (You need to specify this!)
If you haven't replaced the coolant temperature sensor, do it. (about $25).
If there are any other trouble codes, fix the sensors. They all cause the car to run lean and will give you very poor gas mileage.

PS, you probably didn't need Cats, more than likely you have a bad sensor setting them off or you need the ECU flashed. There is a TSB for this.

Andy