The city in which you have a harbour must be connected to your capital IIRC.
Note that you need a tech (is it Magnetism?) to trade via ocean squares though.
Same for sea tiles. Forgot witch tech though.
After spending ~1000 years trying to repair my rep in that game, I pretty much haven't traded in such a way as to have to worry about it - IOW, no trades where I was giving a resource in a 20-turn deal overseas. Now that I see how it works, though, I can (hopefully) make better use of it.