How good is your mechanical skills and if you have basic handtools? We can help you DIY. If uncomfortable doing the job yourself, then at least advise your mechanic to at least check the following:
-Knock Sensor - typical resistance is 550K ohms (500K-620K ohms). Connector is on the front driver side. If the KS is original, then most likely, it's due for replacement. Usually, it fails open (infinite resistance). So if the resistance is too low or open, replace the KS. It's possible that the bad EGRC Solenoid Valve (P1400) caused rough idling and triggered the KS code (P0325). If KS resistance is withing range, replace the EGRC solenoid valve first, reset the ECU and see if the KS code comes again. OEM @ $45.
-EGRC Solenoid Valve - controls the EGR Solenoid Valve and can cause rough starting engine operation if failing. Spec for resistance is 30 ohms. The Solenoid Valve has a green connector near the Throttle Linkage and 3 tubings, secured by a nut under the housing (it think the nut is 10mm). Given the age of your car, you need a heat gun or hair drier to pull out the tube from the Solenoid Valve fittings.
-the 96 Maxima has 3 O2 sensors - 2 front and 1 rear (99-CA and 2000 onwards have 4 - 2 front and 2 rear). In my experience, I have not seen O2 sensor causing rough idling/engine operation. Usually, it results to rich mixture and thus poor mileage (and may damage catalytic converter). P0130 indicates problems with Right Bank (Cylinders 1-3-5) Front O2 sensor, related harness, etc. At normal engine operation, @ 2000RPM, the front O2 sensor signal should fluctuate from >0.6 VDC (Rich) to <0.35 VDC (Lean). Replace if out of range.
Please refer to the attached link for more information about description, trouble codes and diagnostic.
http://www.nicoclub.com/FSM/maxima/1996/EC.pdf