Hello there
First, I'm sorry to bring this topic up, but since I have a very similar problem to the first post, I think it fits more to keep the conversation in here rather than creating a new topic.
So, my problem is pretty much the same of iHex, with a few differences. The common thing is that I had a problem with my SD (it couldn't save anymore) but my Pokemon game said it saved, so after that, the date of the save on the SD and on the pokemon game didn't match. I changed my SD, and pretty much any other game worked fine with a single copy of the problematic SD to the new one and put on the 3DS.
The difference are that my game is Pokemon X (digital one, which I don't think it would be much of a problem to do the things to try to recover it). But the other difference is that my 3DS does not have a CFW or homebrew. It's pretty much from the factory (only with the official systems updates).
I do not think I formatted my 3ds since this problem happened (although I think I uninstalled and reinstalled Pokemon X). But in order to do the tasks to try to recover it, will I need to format it? (specially to put CFW/homebrew on the 3DS).
Edit: just to be clear, since I didn't do anything to my 3DS (in the cfw/homebrew thing), It's an encrypted 0000001.sav file)