Odd error when trying to repartition internal SSD

I posted this in the Apple Discussion Communities but I'll post it here too in case someone here is able to help me

I'm trying to reset my Macbook Air rev. 4,2 (Mid 2011, Thunderbolt port) to factory defaults because I decided that having BootCamp and Linux running together was not what I wanted.

After using Disk Utility to remove the partitions created during the Windows install and split Linux install, I realised that something went wrong and it was a bad idea to do it manually - Boot Camp assistant can now no longer use the disk, and I get this weird error when using diskutil to verify the internal SSD:

$ diskutil verifyDisk disk0

Started partition map verification on disk0
Checking prerequisites
Checking the partition list
Problems were found with the partition map which might prevent booting
Error: -69770: Partition map check failed because no slices were found


Using diskutil I get this:
$diskutil list

/dev/disk0
#: TYPE NAME SIZE IDENTIFIER
0: GUID_partition_scheme *251.0 GB disk0
1: Apple_HFS Macintosh HD 250.7 GB disk0s1

Oops! Looks like I managed to delete my Recovery HD somehow when deleting the Boot Camp and Linux partition... no idea how this happened either. I certainly didn't want to...

I can still boot into OSX just fine, and I can partition the disk... it appears to work until I try to use Boot Camp to install Windows again - still no luck.

I have nothing important on the disk (using it for apps only and I can reinstall them easily) so I tried reinstalling Lion using Internet Recovery (since I no longer have the Recovery partition...) but it refuses to reinstall Lion because of the aforementioned error. I have GPT fdisk installed on my system and I believe it can recreate the required partition map for reinstalling the system but I'm a bit afraid to do that since the SSD appears to have these 'invisible' slices. I don't really want to end up with a bricked system.

Any ideas on how to proceed? Many thanks in advance!

 

Found a workaround that involves nuking the entire SSD and reinstalling from scratch, for those that encounter this problem this is the only way I'm afraid ; I tried everything else...

There's no option but to boot from a recovery CD/internet recovery (Command + R before the Apple logo appears at startup) and use Disk Utility to reformat the entire disk and then reinstall Lion. Of course, make sure to have backed up anything important to another drive before you do this because you will irreversibly lose your data (since reinstalling Lion will likely overwrite existing data on the disk).

Hope this helps someone eventually (if it doesn't so much the better you haven't nuked your system like I did! )