Dave,
Right or wrong, it sounds like the dealer really hasn't given you enough information to feel confident about the repair. There is a code generated when the ECU isn't getting the expected readings from the front and rear oxygen sensors, and the CEL will come on. I'd get a second opinion, as catalytic converter failures aren't that common, unless you've been using leaded gas, or let the engine run poorly or out of tune because of some other problem for a long time.
If your car has less than 80,000 miles on it, the cat may be covered under the emissions system warranty.

Good luck,

Mark