This might sound dumb as well, but did you do the Spark Plug change after it started running bad or before? I have the Autolites and after I installed them, correctly, the car has ran so good! However, when I first changed them, I accidentally switched the around two of the middle plug wires giving me the same result you describe. I realized this when I took them back out to check for fouled plugs and smacked myself for being an idiot!
I also second the notion for the O2 sensor but you said you already changed that. EHA Valve was the second biggest improvement in starting and idling. I had 187K on my '91 W124 when I did this. I'm sure it will be something simple. Maybe rotor or distributor cap as well...

Good luck.