I'm sorry but it appears to me that you have been ripped off. $2K is a lot of money. Your original mechanic has diagnosed it correctly - P0135 (Bank 1 Front Heated Sensor), probably after an OBD II scan. However, after replacing the O2 sensor, he did not verify its operation.
The dealership did such a bad job, IMO. You said they broke the bolt on the flange. When that happened, I presumed it caused an exhaust leak which caused the O2 sensor signal to be erratic. The O2 sensor voltage, under normal operation, swings between 0.45VDC (ideal fuel-air mix) to >0.6 (rich) and <0.3 (lean) several times per minute. Due to exhaust leak, the O2 sensor was exposed to higher than normal level of O2 from the atmosphere (lean signal) so there was little or no voltage swing at all, causing them to diagnose it as problem with the pre-cat. So replacing the pre-cat(s) will not fix the problem unless the leak has been fixed.
DTC P0135 - B1S1, indicates an abnormal current flow in the O2 sensor HEATER CIRCUIT, as seen by the ECM. This could be a problem with the O2 sensor (open heater element), harness (open/broken wiring) or ECM (unable to control heater power).
The 3-wire heated O2 sensor receives power thru the Ignition Switch while the ECM turns ON the heater (below 3600RPM Auto/4000RPM Manual) and OFF (at higher RPM). With the car at Idle, the O2 sensor heater must be turned on by the ECM. Speed info is provided by the Camshaft Position sensor to ECM.
The B1S1 O2 sensor is mounted on the Bank 1 vertical pipe with connector on top of the engine, rear, pax side. There are 3 wires/pins - Pin 1 is for Heater Control from ECM (L/Y-Blue wire with yellow stripe); Pin 2 is for the sensor signal (W-white wire); and Pin 3 is Power thru Ignition Switch (R/B-red with black stripe). The ground is just thru the shield on the harness.
The FSM recommends measuring the voltage from the ECM connector - Pin 119 (L/Y) and ECM ground. I believe you should also be able to check the voltage from the O2 sensor connector side (top of engine, rear). With engine at Idle, Pin 1 (L/Y) to ground should read 0-1VDC (heater turned ON by the ECM). At higher RPM (>3600/4000) the ECM turns OFF the heater so the voltage on Pin 1 should be the battery voltage (11.-14.7VDC).
Since the sensor tested OK, then the problem could be on the harness (open) or the ECM (no control thru Pin 119l). Check continuity of the harness between Pin 1 of the O2 sensor connector and Pin 119 of the ECM connector. If there is no continuity (open circuit, infinite resistance), there is a break somewhere in the harness. If continuity is good (0 or low resistance), the ECM is bad or the connector pin may be dirty, broken or 'pushed.'
In this situation, they can replace the O2 sensor a million times and it will never fix the problem
Here's a link to the FSM. Go to page EC-205 onwards (Engine Control System) for the wiring diagram and additional info.
http://www.nicoclub.com/FSM/maxima/2000/ec.pdf