Rectifying Social Security Identity Theft?

VxSote asks: "A 19 year old kid tried to buy a car only to find out his SSN had been stolen and used by a terrorist. Now, after talking to various government entities, he is no closer to having his (presumably) good name cleared. So this situation begs the question: how exactly does one go about fixing such a mess?"