My guess is that you had a high pitched squeak from your Prius every so often. Mine (on my 2001) was usually when I started from cold, and occasionally when driving (usually accelerating up a hill). I had the squeak long before I got a check engine light. When the light first went on, I had the code pulled, and it was as I expected: P1436. By the time I got to the dealer, the light had gone out, and they claimed there were no codes. I had the light appear 2 more times, but I had to keep cancelling as the light would go out. Over a year later (two weeks ago) the light came on and stayed on, and I wasn't hearing the squeak as often. Made an appointment, and the code was finally pulled.
$1800 service, covered for free under the federal emissions warranty (96 months/80,000 miles). It looks like you're over mileage for it now, though.
US TSB EG015-02 http://autos.groups.yahoo.com/group/toy ... 015-02.pdf
Aug. 2, 2003, M.I.L. "ON" P1436-HCAC Bypass Valve Improvement, 2001-2002 Prius. (road salt may cause issues with valve. possible fix is to replace the Front Exhaust Pipe Assembly if any shaft binding is evident.)
My understanding is that the catalytic converter is part of that front exhaust pipe unit.
Perhaps you can cite this, and ask for some help in coverage since it was a design problem? ask nicely, and see what happens.