So it's not implausible that a superintelligence could restore even a moderately damaged brain.
Intelligence is not magic. Information that no longer exists cannot be reinvented with fidelity.
For a real example, think of image restoration of natural scenes. A photograph is not a random matrix of pixels, it belongs to a very small subset of all possible images, and that knowledge allows seemingly "impossible" tasks of focusing, enhacement and all that.
And yet still-shots are limited to their original resolution; anything further is artistic rendering and not a valid reconstruction of the original. It is possible to "enhance" the resolution of a still-shot of a video feed of a person's face. It is not possible to "enhance" the resolution of a single still-shot of a person's face.
Memories are tricky things. We do not, now, know exactly how high the fidelity needs to be to sustain a person's "actual" psyche. If information-theoretically significant portions are missing, no amount of genius can resolve that.
For the same reason you cannot extrapolate from the number 3 to the function f(x) whose derivative of x is "3".
You can integrate it with initial conditions though and just like we can use our prefrontal cortex to predict the probable initial conditions of events(albeit inaccurately occasionally), a powerful computer may be able to predict our complex mental pathways based on known past events with high fidelity. I'm not saying that you wont need the initial conditions to integrate the function, I just think AGI would have less trouble with it than you assume. I think you have a good point about the principle though and I will take informative decay into my perceived utility of cryonics in the future.
I know celebrities cryocrastinate just as much as anyone else, but King seems like the kind of guy to go through with it.
http://www.cnn.com/2011/12/02/showbiz/larry-king-i-want-to-be-frozen/index.html?hpt=hp_t3