When terrorist attacks happen successfully, and enforcement agencies had some prior knowledge of them, people blame the agencies. So surely when there is some evidence apparently linking somebody to a planned terrorist attack, the agencies are duty bound to at least investigate it. Of course, they're also duty bound to investigate it within the law, and if the investigation turns out to be unfounded, they should forget about it. That's not what happened here, and that's the problem.
The fact is, this was not just some bloke of a bureaucrat from New Zealand who happened to be targeted as a terrorist. He grew up in Fiji, and his best friend was a high ranking Fijian military officer. Their travel patterns aligned. They had membership in the same group (yeah, it's a "pro democracy" group, but is a terrorist group going to call themselves "pro terrorism?"). They made allusions to stabbing the leader of Fiji.
If the initial evidence was based on any one of these factors in isolation, I can see how pursuing the case would be a waste of time. However, it seems what landed Fullman on the radar was the combination of all these factors. He had the right background (pre-coup Fijian origin), relationships (high ranking Fijian military friends), travel patterns (back and forth at the same time as an ousted military officer), and resources (again, friends with a high ranking military officer).
Had he actually been planning an attack, and the agencies sat on all this information, how would that look afterward? It would look like an agency failed to do its job in preventing the violent overthrow of an ally.
I don't fault the agency for opening an initial investigation. There was plenty of evidence to warrant at least looking into the guy. What seems to be the problem was the extrajudicial revocation of his right to travel and do business, before any corroborating evidence existed.
Wouldn't the proper way to handle this investigation have been more covertly? Sure, scoop up as much data as you want -- just enough to see if he actually is planning an attack. But why remove his passport? Keep him under surveillance and watch for any sudden moves, sure. But why the need to restrict his travel? What purpose does that serve?
And once they found the investigation was unwarranted, they should have immediately dropped it. Had they done this covertly, the guy never would have known he was even under surveillance. But instead they seized his passport and many of his possessions before having the evidence to do so. He was fully aware of the investigation in such a way that it materially and negatively impacted his life.
To be fair, though, they did handle the aftermath in a somewhat commendable fashion. They lifted the restriction on his passport without any further hassle, within two years. That's pretty quick. Perhaps they should have done more (apology, compensation), but even by US standards that seems like a fairly equitable outcome. He never went to prison.
At the end of the day, it sucks for this guy. He was in the wrong places, with the wrong people, at the wrong times. But I have trouble faulting the agencies for their initial suspicion. It's their handling of the aftermath that I have a problem with.