I have 2 Overo Air in the same situation, when I boot them NAND sometimes boot correctly, but most times it hangs in Uboot, after I2C is checked. May be the problem in the DRAM?
I have flashed it many times (booting from microSD), but it's the same situation.
Texas Instruments X-Loader 1.4.2 (Jul  8 2009 - 21:19:00)
Loading u-boot.bin from nand

U-Boot 2010.09-rc2 (Sep 29 2010 - 11:53:31)
OMAP3503-GP ES3.1, CPU-OPP2, L3-165MHz, Max CPU Clock 600 mHz
Gumstix Overo board + LPDDR/NAND
I2C:   ready