Well, assuming you didn't try putting leaded gasoline in your car (just kidding) and your oxygen sensors are working fine, I think that you either you still have a leak in your exhaust or you have a faulty coolant temperature sensor.
When you said that your mechanic replaced the catalytic, did he just cut it out and put in another one? Or did he do a direct fit replacement? Because when you do a direct-fit, you have to replace the whole y-pipe from the manifolds and the flex pipe. I would just check the exhaust for any leaks. This is the magnaflow direct fit catalytic for the Avalon:
http://www.car-sound.com/02product/d...irectfit=23880