I think you need to explore the sea route all the way up to the tiles about two tiles off the other civ's harbor. This can get pretty hard to do when the other civ's cultural boundary extends half a dozen tiles out to sea. And if you can afford it (meaning when you're in a deadlock on the main island with 150 cavalry and infantry, but don't want to go to war,), you can always set the research bar at it's highest and go all the way up to Flight for airports, just land a settler somewhere on the other civ's island and start trading.
That happened yesterday to me. The Aztecs had their own BIG island (I think they conquered the Persians, since some of their cities have Persian names), and I just landed a settler and rushed the Airport and a Temple. Problem solved, and instant trade routes to three new civs.