Nissan Repair: Start up, nissan maxima, grade fuel

Question
I own a 1998 Nissan Maxima. It runs great, whether on the highway or in town. The problem I have is when it starts up. When you go to start it up for the first time of the day it is hard to start, and it makes a fun noise. It sounds like the starter is not disengaging after is has turned over the engine. I have had the car over a year and when we bought it the check engine light was on. I had it checked out, they said it was a oxygen sensor. I called my mechanic and was going to have it fixed but the light went off. I think it was because I was using the higher grade fuel. The light stayed off until about July. Gas prices were up so I was using cheaper gas. I had the light checked again and it was the knocking sensor. I put higher grade fuel in and called my mechanic. Before I could make it to his shop the light went off again. Now the light is back on and I am still using the same grade fuel. I have only be late once with an oil change, and I put new tires on the car. It has around 135,000 miles and we put 31,000 in the last year. I would like to get the start up problem fixed and give the car a tune-up. So my questions are: Do you know what is causing the starting problem? What should I do to make sure the car gets a good tune-up? And should I fix the start up problem before or after the tune-up?

Answer
Cameron,

The starter is going out and they all do since it is a gear reduction starter.  It gets dry and you could take it apart and lube it but it would cost so much in labor I would just to a rebuilt and be done with it.  The check engine light is due to the quality of gas.  Premium is best for your engine and the lower grade will set the light.  You could disconnect the battery and let the computer drain and try the cheap gas but there is no guarantee that it won't come back on...