My FSM lists the following to check in order:
1) Any other codes? Check them out first
2) Use a scan tool to read the output value of the A/F sensor
3) Check for open/short in harness and connector between A/F sensor and ECM
4) Check resistance of the heater in the A/F sensor
5) Check the air induction system
6) Check fuel pressure
7) Check injector injection
8) Check gas on exhaust system
9) Replace A/F sensor
10) Check to see if you still get P0125 -- if so, replace ECM
11) Did vehicle run out of fuel? (running out of fuel will cause P0125 to be recorded)

Seems to me like step 11 should be step one -- P0125 could be caused by lack of fuel (plugged lines or filter, weak pump, etc.)