I would have to watch again to make sure this wasn’t what I was reading into it, versus the character, but I took it as follows:
[spoiler]Grindlewald had been a major force in Europe, and Newt had worked for the Ministry of Magic in England.
Newt also had several occasions to talk with the big bad in disguise, and his language was very familiar. The one on one scene in interrogation? He specifically calls out the leading questions as 'I’m not some Grindlewald acolyte’
The railroading punishment, the rejection of alternate hypothesis, the fact that during the trial he could have easily stated ‘yes, she did come to report this yesterday but was ignored’ (though this may have been a plain old plot hole)
The final confrontation did lead to certain conclusions. Having Newt’s companion have a history with Credence, and some repertoire, makes his reactions stand out.
Newt was also an acolyte of Dumbledore, whom you may recall was a onetime close partner and friend of Grindlewald.
All in all I did not find his conclusion unreasonable from his position. I think that his interrogation should have been enough to arouse that suspicion, and seeing how he interacted with the boy, and his overall sketchy behavior, made it make sense to me. Had newt not been part of the Ministry of Magic, had Grindlewald not been a major factor in Europe for years, it would probably have bothered me. However he was these things, so it merely made him intelligent and observant of the available evidence.[/spoiler]
Now as the audience we have a few other clues to tip us off. But Newt wouldn’t have seen the opening credits like we did.