I recently spent (i.e this evening) over 1.5 hrs on the phone with Apple technical support. I am not one to usually call support but here was the issue.
I was having trouble with my system around three days ago and decided to wipe the 2011 MBA after making a TM backup. After wiping the main partition I could not restore the OS via the Recovery HD option due to an error message. "What the heck I thought, why not use the newfangled internet recovery feature." I wiped everything and made one new partition on the MBA in the sig. It starts internet recovery, I connect to my WiFi and BOOM....nothing happens. Wait for it....nothing. Globe spins, network selection choice with full bars, then...nothing. After trying this forever and browsing the web for a solution I call Apple technical support to see if something needs changed with my router/network settings (firewall/ports/etc). They finally decide after 1.5 hours that I have three options.
1. Take it to an Apple Store for reinstall (nearest one is 2.5hr drive)
2. Send it in to them for reinstall (at least 1 week turn around without my main laptop)
3. Pay them for a full Lion reinstall disk and they would send it to me so I could do it myself.
I could not believe what I heard. I sat on the phone with you for that long and you offered me that? I clarified with the rep that since Apple chose not to include re-install media with the laptop and decided to implement a new "recovery feature" that was not working correctly I must now pay again for an OS on a system that I already bought an OS for?
She confirmed my statement.
Ultimately I decided to send it in (now I have to wait for a box). I have usually had excellent service from Apple but this really irritated me. Sorry for the long rant.
As others have suggested call back and request escalation. Seems to me they can overnight a recovery USB to you. Be persistent and keep escalating.