I've never had this issue before... I gave Lion Internet Recovery 2 hours to download Lion and re-install it. I checked on it at the start, and after 2 hours. The times to download were: 52 hours 2 minutes and 11 hours 49 minutes. Since it did not complete in a reasonable amount of time, I cancelled it and shut down the MBA... now it boots into Internet Recovery automatically, goes through its 15-minute boot routine, tries to install Lion, fails, automatically reboots, ad infinitum. Should I format the SSD in Disk Utility before trying again?