There were no trade routes. This was the Classical era, and I had just met the AI that caused the influence change in my cities one turn before this dramatic change occurred. I had no trade routes with the only AI I had met up to that point (to my west). I had trade routes with the human player to my south. That player had trade routes to me, but not to the AI to our west. The other human had not yet met the AI who influenced my religion. The AI to my west had not met the new AI, and had no trade routes with the newly discovered nation. This wasn't a trade route issue. 

It was, as someone said above, probably due to the fact that I had harbors. There are several reasons this mechanism ends up feeling buggy whether it's intended to be this way or not:

1. A dramatic one-turn change in a game based on incremental gains

2. No clearly visible reason for the change

3. The one-way delivery of the change was (almost certainly) based on the newly met AI's ideology. That AI was one notch leaning toward Tradition (gives +2 faith on every territory, more powerful than either of the first two religious tenets [Shamanism, Polytheism]). This ideology position is gained from things like selecting cats instead of ferrets (a stupid, frivolous "event") and selecting a civic for +1 science per researcher instead of +1 science per trade route (something that has nothing to do with religion). The AI had also selected a civic that gives -50% on creating outposts instead of one that gives -20% on attaching outposts (again, something that has nothing to do with religion). The only civics choice this AI had made that could have affected religion was selected so it did not improve religion (Founding Myths - Natural Right instead of Divine Mandate). TLDR: civics and events that have no logical connection to religion substantially affect religion for no good reason at all

4. Religion supposedly spreads even though my borders are not open to this AI. I get that trade and places of trade (harbors) are historically sites for culture exchanges. However, this is a game where a closed border means my real units cannot set foot inside someone else's country or their bordering waters unless I'm an expansionist. It's a double-standard to have the invisible evangelizing minions of a non-expansionist invade my country en masse from 1000s of miles away in the absence of any real reason for those people to be there and in the absence of me even allowing them to be there. If we say, "no, a scout can't enter this AI's territory because the borders are closed," we should also say any unwanted evangelizers on boats from a country that doesn't have open borders are rejected along with the ship on which they arrived.

5. Having a harbor alone should not cause this because it puts the player in a position where the only way to avoid it is to not build harbors. Telling a player they shouldn't build harbors so they can protect their religion is silly in the absence of other tools to protect their religion.

i feel the root of this issue, like many other that feel "broken" or "buggy" or "cheaty" is the absence of a clear, in game explanation for the mechanics

i understand that there's an attempt at NO SPOILERS going on, but there are situations like this that ruin the experience not because they're bad on their own but because they provide no information to predict and prepare

to me, it was the huge bonuses AI gets in humankind difficulty level. until i was presented with the information that it is not available anywhere in-game, i felt frustrated as i was not able to understand how was it that i had to defend against a stack of 4 swords before turn 25

civics unlocking is another area i feel falls into the same problem but at least they're now mostly well understood and posted for anyone to have at look over at the wiki

i honestly believe that lack of information is detrimental for those players that enjoy to dive deep into the different game mechanics. i understand how casual players can feel overloaded if there's too much data to process and i also think unveiling stuff in a narration style is a nice design choice. i just hope there could be more "advanced" info available to help make sense of the less intuitive systems of the game