Yup, they're right. You'll have trouble finding *any* shop that will remove or ***** around with your emissions hardware because it's a federal offense and however much they charge you won't make it worth the hassle/risk to the shop. You can get header collectors that already have the **** for the O2 sensor welded in so that's not a major issue. Just be careful about lengthening or shortening the wires that go to the sensor because changing the length of those wires can sometimes (depending on how the ECM is programed) change the info the ECM gets from the sensor (on some systems the info coming from the O2 sensor is based on voltage/resistance and changing the length of the harness going to the sensor changes those values)
Having said all that what a lot of guys don't realize or take into account is that sure, early catalytic converters DID restrict exhaust flow resulting in lost performance but that was back in the 70's. Modern systems really don't suffer from those problems and removing the converters doesn't result in ANY performance gain. If you*are* determined to remove the factory setup then the best way to do it is to either stick with an aftermarket cat-back exhaust or to install a complete new one consisting of headers, free-flowing cats and dual exhaust. If your state has emissions testing then I'd stick with headers & a cat-back installation. The dual converter systems are there because that's what you need to meet emissions requirements (the first converter works while the engine & primary converter are cold, once the primary converter "lights-off" it handles the majority of emissions.) Cutting out the converters really doesn't net you any horsepower and just isn't worth the annual hassles of trying to pass inspection.
/emoticons/
