Justin, maybe you have a faulty O2 sensor. If that were the problem, it would be completely coincidental with the new MAF being installe. But historically, O2 sensors are prime candidates for lean OBD2 codes, at least when the stock MAF is retained.
-Kurt
"I'm a little sceptical of that internet thing. After all, what's it got besides information?" -DB, 1/97