Lion Recovery Terminal will not allow me to run TestDisk? Setup: Macbook Air (2011) running Lion with BootCamp (Windows 7).

Problem: I have somehow screwed up my partition table. When I boot I only can select Windows instead of Windows and Lion. However Windows gives a BSOD regardless of safe mode option selected. 

My Attempt: I have booted into Lion Recovery and tried running Disk Utility to repair disk volumes but it fails. Also tried to reinstall Lion but unable to because Lion doesn't recognize disk volumes (however it does see that there are two main partitions but they are grayed out). 

I have data on both partitions I would like to recover so I am trying to use TestDisk to rebuild the partition table, but when I launch TestDisk from my external thumbdrive I get "Illegal instruction: 4".
Have you tried booting from a Linux LiveCD (well, instead of a CD, you'll need a USB thumb drive, but it's the same idea)? From there you could copy data to an external hard drive and just wipe the internal hard drive and reinstall.

If you have another Mac laying around with Thunderbolt, you can boot your Mac into Target Disk Mode (hold down T while booting), connect the Macs together with a Thunderbolt cable, and perform any disk recovery from there. (You might be able to go to an Apple Store and use one of their Thunderbolt Macs to recover your drive; they can be surprisingly permissive at times.)