Reinstall on Macbook Air 2010 (Macbook 3,1)
Finally, issue was solved. I burned my recovery partition from my Mountain Lion Macbook Pro onto a USB drive, and used that to boot into recovery and downloaded and installed Mountain Lion on my Mac Air, successfully.

It seems that this generation of Mac Airs have some kind of protection that will ONLY let you use a recovery drive to boot from USB and even from the drive itself.