Why can't I no longer boot into my MacBook Air? My MacBook Air (Late 2011) hangs during startup at the Apple logo, and the spinning cursor freezes.

I have booted into verbose mode and it hangs after the following messages:

com.parellels.kext.vnic 7.0.15054.722853 has started    
MEDetect: PASSED - ME_INTERNAL_STATUS: 0xfred1f338 = 2
nspace-handler-set-snapshot-time: 1326447352


I have tried resetting the PRAM, logging into recovery mode and repairing disk permissions, and starting in safe mode but still to no avail.

I performed a Parallels Desktop update last night. I wonder if this is preventing the machine from booting.
Looks like there's a reference to parallels and it might have modified something in the directory. 
You can do a re-install which shouldn't wipe your data. 
Startup with CMR+R and just re-install the OS. Don't choose the option to erase.