I have the 11" MBA but I use it 90% of the time connected to an ancient 23" Apple Cinema Display with a DVI adapter. When I first got it, once or twice I had a similar problem but it hasn't happened again.
For me, I assumed it had something to do with the Seagate hard drive/dock connected to my MBA via thunderbolt. The monitor plugs into the dock and the jack is recessed very deeply so it may not have been making good contact.
There were several threads here about HDMI monitor problems on the MBA but I never saw any followup posts. I don't have any problems with that either on my MBA.
Is there any way you can try a different adapter/cable/monitor to localize the problem?