A few weeks ago my cousin recovered his Gamertag on my Xbox 360 because we were playing Xplosion Man at my place and he wanted to get the achievements. Some time after, he started playing Red Dead Redemption at his place (and in his Xbox), getting almost all the achievements. Because his Gold membership had expired, he didn't bother to recover his Gamertag on his console, but when he finally did, all the achievements he had gotten on Red Dead Redemption were lost.
Is there any way to get them back? His game files are OK, so now it looks like he has 100% of some stuff but no achievements to go with them.