Yes, you're right. It should run without it.

The aftermarket "generic" O2 sensors sometimes cause a Check Engine light. If you were seeing Check Engine before the sensor was replaced, try to look at things like the crank position sensor and fuel pump relay. Those are wild guesses, but not being able to eliminate the codes you're getting from the diagnostic unit, it's hard to speculate otherwise. If the problem coincided with the codes appearing in the diagnostic memory, it would be different.

Once the shop tells you what they find, post back here (if you have the luxury of time). If you're getting hosed, a bunch of people will tell you so!