yeah, I guess one can't have two tenses in the same sentence. I hereby change my sentence to:

Я увидел мужчину, с которым была девушка

I saw the man, with whom was the girl