Lion Internet Recovery Problem
If you have access to another computer, you could try downloading the Lion installer from the App Store, right clicking on it and clicking "Show Package Contents" and finding the "InstallESD.dmg" file and restoring this to a flash drive (8GB+). Then you can hold alt on startup and select the drive as your boot option. You should be able to install Lion on the air without needing to download the additional components, but it may still try. Even if it tries, it might still work since you're installing from a different drive. It's worth a shot.