O2 sensors are usually fine for about 150,000 miles, at which point, they should be replaced, as I did with my CV Sport. If I was having these symptoms with my car, I would certainly think that the MAF sensor is more likely the culprit.

The original poster can also do some diagnostic tests of his own on the MAF sensor, providing he has a voltmeter.

I do, in fact have one.
when I get off of work I will test it.

So the maf can cause stutter and other symptoms?

Yes, it most definitely will.

Also, which cats were removed? If only the backs have been cut, no issues should arise. If you removed the front pair though, that will throw a CEL.

Well cleaned and tested maf, it tested well.
I'm smelling major fuel being dumped, and it's heating up the cats, on both sides..

There's only a few things that can do this correct?