Do you remember what the service code was ?Sounds as if the car may have gone into limp mode or with the O2 being bad may have caused the plugs to go bad also.Id get the O2 changed and see how it drives/run's.Best site ive found for an O2 is at
www.rockauto.com for 54.79 Standard Motor Products part #SG273 .Please dont use a BOSCH as they can be problem's later down the road and either giving false reading's or failing.Dealer cost on a stock O2 is just over a 100 bucks.
If you have any other question's just shot me a PM,since I spend most of my time over in the GrandPrix Fourm.
~Larry~