disconnect the plug to the lambda sensor, does it run ok? if not, the problem is elsewhere. if it does run better then either the new lambda is faulty or the wiring is shot.
have you cleared the codes then checked to see what comes back. look in the ecu measuring blocks too then you can see what the ecu thinks the coolant and inlet temps are, as well as read the throttle position to make sure thats ok as well.