update:
1. Called Support... and it didnt really help. basic troubleshooting etc.
2. continued my testing - restart CMD + R and connect to my office wifi (yesterday was at home) and start downloading the installer. after a while, got the installation popup prompting me to install, click next, then got finally to download the Lion source. However, my connection in office is so slow it was taking 7hours to get the whole thing.
3. I thought that the guy at the end of the line did something miraculous... I then disconnected and went back home trying the exact same steps... and I was impossible to get it work !!
This is really amazing, the worst piece of crap I have ever seen. Brand new macbook air shipped with Lion installed and I can't get to reinstall the whole system ?!? This is really ridiculous !
Another part is that I tried to install Snow Leopard from the USB key (provided with earlier mba 11") and it can't even get to the installer... that's another point...
Apple, can you get a fix?