Translation:I had never found that I was famous until that moment.
Both would be viable, but the one you are pointing out is the most common in conversations. Also "me tinha" sounds phonetically like "metia" which sounds badly to protuguse speaker, since "metia" translates roughly to "shoving into..."
I thought Past Perfect was strictly 'imperfect tense + past participle'. So is it ok in general to have an object pronoun in the middle?
I put, "I never had found that I was famous until that moment." and it was marked wrong.
Using never had is wrong in that sentence, I think. The correct is had never.