Can you read live data with your scanner? If so, it would be interesting to see what the PCM is reading as the coolant temperature. That could implicate the CTS and its circuit.
P0125 - Insufficient Coolant Temp For Closed Loop
P0130 - O2 Circuit (Bank 1, Sensor 1) lean
P0133 - O2 Circuit Slow Response
The 130/133 could be the result of the PCM not achieving closed loop mode and trimming fuel appropriately.