No filme Macacos 12, in 1990, when Kathryn is meeting Cole for the first time in her life, she says:
James, where did you grow up? I have the strangest feeling I've met you before.
What is the implication of this? How could she have met Cole before this moment? Only Cole is the time traveler and as a young kid he's seen her at the airport.
Why does Kathryn feel that she's already met Cole in 1990?
You are right in your reasoning that in 1990 there was no time before yet when Kathryn could have met Cole. She only sees the young Cole in 1996 at the end of the film. However, I think there's two viewpoints we can approach this with, both hinged on the fact that the film presents us with a (largely) immutable timeline where the past can't be changed and everything that's going to happen vontade acontecer.
There is actually a way she could have seen him before and later in the film she realizes where. When Cole vanishes after kidnapping her, the police tell her that the bullet from Cole's wound is from World War I, which then makes her dig out an old photograph (from her own psychology research on doomsday prophets) which shows the naked Cole in a trench in World War I. This is what makes her suddenly believe his story. While she poderia have seen the photo only after 1990, there's nothing that precludes her from working on this stuff even before 1990. It's also unclear how much of an impression this photo might have made on her, but it's clear she knows it and has seen it before and immediately digs for it when hearing about the bullet. So the photo might very well have made at least somewhat of a faint impression to her.
But there is even more to it, if we extend the film's immutable timeline approach into a more metaphysical direction about fate and how not only humanity is doomed to bring its own demise but also how Kathryn's and Cole's lives are inherently bound together to this story. This is emphasized in the film when Kathryn sees young Cole at the airport when old Cole dies and how Cole dreamed about her his whole life beause of this.
It's the same dream I always have... I think it was always you.
In light of this entanglement of both their fates, we can see her little throwaway comment also as a more symbolic foreshadowing of this, an abstract feeling of familiarity, even if there was no actual way for her to ever have met him.