First, a preface:
"I hate temporal mechanics" - Chief Petty Officer Miles O'Brien, Deep Space Nine.
That said: the fact that Matsumoto didn't disappear is not prima facie evidence that he is lying. For that to be the case, the timeline would have to be singular and monolithic. It is the timeline, no alternates allowed, the one singular future is irrevocably changed and the previous one ceases to exist if the past is changed.
But as many stories have shown, including Avengers, that isn't always the case. When you time travel, you create a new timeline. For sure, if you do absolutely nothing, most if not all of the history as you know it will play out pretty close to the same way. As Terminator (and countless viz novels, lol) showed, there are multiple routes to the same future. Matsumoto's foreknowledge will very likely become less and less reliable as time goes on (and arguably should, keep an eye out for it), but events may still lead to the disaster he's trying to prevent. That one politician's survival may not prevent (and very likely, will not) prevent the AI Naming Law from passing. Much like Miles Dyson didn't create Skynet, but someone else ultimately did.
Ultimately time travel stories always create a paradox. It's up to the writers to make the story compelling enough for the audience to forgive it. With just the two episodes, we have yet to see if they can achieve that.