i think he's passing thru an ocean tile, not pure coast. he's allowed to since it's within his borders, but you weren't of course. i can't tell from the screenshot whether it's coast or ocean. you do say that's from earlier, before he got culture access. did he come from there that early, or only after he got culture? if only after, i'd bet you a great prophet there's not a "coast-only" connection there. turn tile yields on is the best way to tell, ctrl-y.
it sounds bizarre that it can be one way but it's true. and not necessarily fair
. here's how it worked in my game:
shaka's yellow, i'm green. those 3 squares that i marked with o are ocean tiles that he's allowed to sail into (because they're in his borders) but i can't enter, even with OB (because of the BtS rules change). and with those two little single-tile islands there, he actually has a coastal connection now to my entire continent
! meanwhile i can't even get close enough to see his cities til i can make caravels because there weren't any convenient islands like that in the reverse. waaaaaaaaah i don't know why they changed that rule. i expanded that direction earlier than i'd planned to once i found out he was so close and able to send settlers on galleys if he wanted to *giggle*.