I'm not sure how they can fix this, but I do think it will need to be addressed if they want to hire and retain top talent. They have interesting problems but no one will work on them if they feel they are, in the end, hurting their fellow country-people.
The other half is admitting that the government did something wrong in the first place, which they can do by prosecuting officials who broke the law, retire those that quasi-legally facilitated domestic dragnets, and pardoning Snowden, Winner, etc.
That’s going to take politicians who aren’t jingoistic.
If I knew a 3-letter federal organization was dedicated to defensive tools, white-hat pen testing, and US infrastructure cyber security, I might consider joining. But the NSA has managed to tarnish its name with domestic cyber spying on US citizens, and that should have been the realm of the FBI, which is supposed to follow laws and can be audited.
We can only hope that NSA actually has some of these types of guys and we just don't know about it. But I'd argue that if the NSA was getting any of those types of guys, they weren't getting very many.
Another thing to think about is the athletics analogy. Schools like Stanford and Northwestern can't get the athletes that a place like Alabama can get. However, they do a good job of training up the athletes they can get to the point where these schools have actually been respectable from time to time. It would be interesting to consider the realistic feasibility of hiring "2 stars" or "no stars", so to speak, and then training them up. (Of course, this doesn't always work. Most schools have teams that suck. That's kind of the danger with the "train them up" idea.)
Stop spying on and collecting all of "Random Joe's" emails and chats, and start targeting people who are actual threats to national security (and don't misinterpret any random petty crime as "national security issue" to give you an excuse to abuse those powers either).
Economic espionage or to help corporate friends should never happen either. No, it doesn't matter that "China does it, too".