Clean install of Lion
From the Apple OS X Lion website:


  General requirements: 
  Mac computer with an Intel Core 2 Duo, Core i3, Core i5, Core i7, or Xeon processor


The MacBook Air 1st gen has a Core 2 Duo processor. source

So it should work.