A stuffed 02 wont make it lean out, it ONLY come into affect as a "Trimming" tool/sensor when your at idle and Cruise to give you good ecconomy (Closed loop) When you are on full power WOT the ECU cut the 02 input.
If the idle if "Gay" then you might have a boost/vac leak, might have knocked something when you was doing the fuel pump? (Or other things?)
My next thing I would check is the compression of the engine just for peice of mind, Just came across my mind cause of you said it was leaning out & with the bad idle, MIGHT have done engine damage.
QUOTE "Ryan came for a drive with me after and we think its leaning out."
How did you know it was leaning out just from driving it? Was it pinging?
How do you know your leads are fine? Best way is to use a multi-meter. My leads "Seemed" fine as well, till I got a new set and the problem went away.
With out looking at it maybe you done some damage to the cradle putting it in? even a small kink in the metal lines will cause a restriction in fuel flow.
But I'd be doing a compression test 1st, to make sure that you have a good base to work with. I have a tester if you need one.
Good luck with it all.