O2 sensor, is your Oxygen sensor, it located in your exhaust pipe that leaves your exhaust manifold, just before the convertor. But since they have already removed your convertor, I don't what effect that would have. Try locating your EGR Valve and see if it is stuck open, a stuck open EGE valve creates a lot of driveability problems.
Let us know how you make out.