Hey there :-),
I just finished my latest one, which really had a "frame of damage" surrounding it ;-).
Because of that, I'm not 100% sure about the lower parts (especially underneath his arms), so maybe you could help me out once again :-)?
Before:

After:

Once again I started by separating the frequencies with my beloved Surface Blur (for a tutorial see the third video here:
http://www.operationphotorescue.org/forum/index.php/topic,2687.0.html) and used a "Normal" layer in between the HIGH and LOW (-pass) to get rid of most of the damage. I also painted in some shadows around his arms to make it look less flat.
This already did most of the trick, but I realized, that if his arm was sitting on something, it'd probably cast a shadow. So I just selected the area in Quick Mask and added a curves adj. layer with a lowered midpoint.
Now I finished the restoration with the clone stamp on the HIGH layer. Modes used were "Lighten", "Darken" and of course "Normal".
This however did not leave me satisfied, so I added some levels adj. layers to lighten the whole image and improve its contrast.
Next I color corrected the image by selecting his shirt of being neutral gray.
There was still some odd magenta on his skin that I wanted to fix, so I used a Hue/Saturation adj. layer, selected the Reds, defined with the eyedroppers and shifted the hue 10 degrees to the right.
Last thing was lightening his face with curves. I pushed the mid tones a little higher, added red and subtracted blue to get the color right.
That's about it :-).
In between I used some supporting layers like solar curves, on which I planned to do a special tutorial for ya (I even did, but Camtasia simply didn't save the files... will give it another go soon).
Edit: To get the right size for his arm, I used the ruler tool and checked the size. I then used that to get the size for the other arm right :-).