Ok my quick story...
I purchased a brand new 15" RMBP last week. Started it up, selected FileVault as part of the OS X first run screens, boom! the "connect power..." problem that I didn't notice until after transferring about 200gb of various stuff and downloading the entire adobe suite...yay.
I tried the "Clear PRAM->Command R-> Unlock Disk-> Repair Permissions (Partition)->Repair Disk (Partition)->Repair Disk (Disk) 'solution' (Thanks Scafede) and managed to get it to encrypt after a short wait but it went back to "connect power..." when it started optimising. I'm maybe not as patient as some because after trying the 'solution' twice more I opted to backup to our other thunderbolt mac (which didn't take all that long), restore and NOT enable file vault as part of the first run.
Today I went to turn on file vault (because I actually enjoy the security of encrypting clients files etc.) and got the "connect power". ***!
Tried the 'solution' again twice and nothing, not even after waiting an hour or so for it to start. Then it occurred to me that I was running in clamshell mode so I opened the mac (left the monitor plugged in), re-ran the 'solution', and it has actually started encrypting again.
Now perhaps it was third time lucky with the 'solution', or maybe it's also a issue with clamshell mode.
Hopefully this info helps someone avoid the hassle of a restore, if in fact the steps I took produced anything except a random result!
Cheers