If all plugs are black, car was running rich.....could be dirty air cleaner......could be bad O2 sensor.....could be a misfire(plug, wire, coil)....could be bad f/p regulator......
I would replace the plugs.....probably the wires too......check the coil terminals for corrosion, arcing.....might as well finish with a complete tuneup if never done(fuel filter, air filter, and PCV)....
If car still runs like crap, do coil output check......
The O2 sensor could also be carbonned up from running rich....
Losing any coolant?
Hopefully, you didn't run the vehicle too long, to create cat problems....especially since, by mileage/time, your cat is just out of warranty.....