FileVault optimizing... 43 days remaining
My wife bought a 11-inch MBA about a year ago. I turned on filevault as part of the setup, and had the same issue. We took it back to the apple store, and asked for a replacement citing the one she as being defective. In the stores, Apple isn't shady - we got a simple swap with smiles. The new one did FileVault2 just fine.  

Everyone should do it exactly this way. As soon as you buy it, turn it on. Before you attempt to transfer any media/stuff to it or install apps. If it doesn't work, take it back to the Apple Store and ask for a replacement or a refund.