Have you listened as Bill suggested to confirm where the noise is? The catalytic converter is the first large part of the exhaust system and will be roughly in the area of under the front seat. If the noise is coming from that area, it is likely the cat that is bad. Kicking it to see if it rattles could confirm that. If you're not sure of any of this, take the car to a muffler shop and they will be able to do a back pressure test to see if the cat is clogged.
The temperature gauges on the dash are not very accurate. How well does the heater for the car work in really cold weather? You could swap out the thermostat to see if that helps, as they aren't that expensive.
With the number of miles on your car, it'* quite possible that your oxygen sensor is at least tired. Bad gas mileage would be a good indication of a tired O2 sensor, and could be replaced and considered part of regular maintenance.
Black 2000 SSEi, Silverstar Headlights, Angel Eyes fogs, 3rd brake light overlay, hi-flo cat, drilled 180 degree thermostat, Intense FWI, PCM, shift kit, and 3.4 Pulley. Solid front mount.