Toyota Repair: 99 4Runner - Check Eng Lt - O2 Sensor?, toyota 4runner sr5, toyota 4runner

Question
I have a 99 Toyota 4Runner SR5 V6 with about 81,000 miles. I recently started having problems with it as follows: End of Aug when I turned the engine on, it sounded like another motor was running very loud over my engine, when I turned my car off, the other motor kept running. Was told it was my starter motor so they replaced my starter($253).  Was told this is common problem with toyotas? In addition, my car was dying out when I would try to start it especially in the morning. Same shop said it was because the Idle control valve had too much carbon build up and was affecting my idle and needed to be cleaned ($81). Don't think I have ever had fuel injection cleaning so this may have contributed to that. Other than above repairs, I have had no other major repair work done and have kept up with all scheduled maintenance. Then on 9/24 about 4 weeks after these repairs, my check eng lt came on. It came on right after I got gas, so I thought it might be because the gas cap was not on tight enough so I tightened it again.  Not sure if that was the problem because once the light comes on for a malfunction it needs to be reset after problem is fixed, correct?  Took my car back to same shop and had them diagnose the check eng lt(no charge) because I thought it may have to do with work they performed earlier and this was what they told me the computer read out said:
P0125 Insufficient temp for closed loop
P1130 O2 S BISI performance malfunction
P1135 O2 S BISI heater ckt open/short
They recommended I replace the O2 Sensor as soon as possible because eventually my car would start to run rough and would affect other areas of my engine.  Said this would cost around $200-$300 but they would not be sure until they looked into it further to make sure that is the only problem.  At this point, I just want to make sure that the O2 sensor is really the problem or could it be something else?  I also wanted to find out what other areas of the engine are covered under the warranty even it's past it's 3 year, 36,000 mile warranty (water pump, catalytic converter, etc.)?  Sorry, this is so long, but wanted to be as detailed as possible.

Thank you very much,
Tishiya

Answer
From what I've read this sounds like a very competent shop you are going to, their diagnosis is absolutely correct concerning the O2 sensor, the bank one/ sensor one should be replaced to correct this condition, and by the way if more of the people that ask me questions were as detailed as you it would make my life a lot easier. As far as warranties are concerned it is out of warranty for just about everything except the catalytic converter and the ECU which are warranted for 8yrs/80,000 miles(federal emission control)