If the o2 sensor was reading rich, then your problem can be caused by
1. Bad MAF (over-reporting the amount of air in the system)...but not sure if your year uses that
or
2. Leaking injector. It's possible that an inner injector valve seal is worn and is consistenly leaking fuel into the cylinder causing it to go rich. The only solution is to replace the injector.
3. Air restriction somewhere in the intake path (filter, Throttle Body...)