I had the same problem about 10 days ago. I tried everything I could think of.
I ultimately created a USB disk with an image of the DiskWarrior boot disk and it worked very well. To do this, format an external USB disk with GUID partitions. Create at least one partition. Then, 'restore' the partition with an image of the DiskWarrior boot disk. (mine is v4.3). You may need to use the Disk Utility option: "Images > Scan Image for Restore..." first.
Now, my system wouldn't boot with a USB disk (possibly yours will, not sure, but if not read on...)
Read this hint from MacOSXHints.com: http://hints.macworld.com/article.php?story=20060301112336384.
Be sure to read the first couple of comments which show how to do this hint super fast and easy. In my case, I booted my sick Mac into OpenFirmware using CMD-OPT-O-F, then at the prompt, I simply typed:
boot ud:3,\\:tbxi where '3' is my special partition. Booted right up into DiskWarrior!
DiskWarrior was able to rebuild the directory of the Mac. (It took awhile, but I'm glad I waited it out.) When I restarted, it booted normally and has been perfect since.
Of course, once you've booted up normally, you can use a retail CD to reinstall in the normal manner for the MacBook Air.