I had the same or a very similar problem. I have a mid-2011 MBA that I upgraded to Mavericks, and then enabled FileVault -- no problems. I then bought a virtually identical used mid-2011 MBA for my wife to use, upgraded it to Mavericks, and attempted to enable FileVault. FileVault would go through the motions of encrypting the whole hard drive (256 GB SSD), and then give the error message quoted by the OP above. When I tried to turn FileVault back off, that would not work either.
I tried re-installing Mavericks several times, erasing the hard drive completely and doing a clean re-install from an external drive, but each time when I attempted to enable FileVault, I would receive the same error message. I called up Apple Support on the phone, and they suggested re-installing Mavericks from the Recovery Partition (not the external drive), but that did not work either. They then suggested I go to the Apple Store Genius Bar to have hardware tests run on my hard drive.
I went to the Genius Bar, and they tested the hard drive, which passed all their tests. As one last thing to try before sending the MBA off to get the hard drive replaced, my genius (Brittney Atilano at the One Stockton Street store) asked if when I had erased the drive if I had ever changed the partitioning. I said no, it still had the original one GUID partition that came with the MBA when I bought it, and I had never messed with the partitioning. Brittney said that in their Apple training, they were taught to change the partitioning to something else, and then change it back to one GUID partition, to ensure complete re-formating of the hard drive. So she changed it to two partitions in a different format, re-formatted the hard drive, then changed it back to one GUID partition, re-formated the hard drive again, and then repeated that procedure once more for good measure, ending up with one GUID partition. We then re-installed Mavericks on the newly-formated hard drive, enabled FileVault, and lo and behold it worked this time, no problems.
I really wanted to be able to use FileVault on this MBA, so I am very happy that Brittney was able to solve my problem. I hope this technique will help others out there . . . good luck!
