If your Harbor isn't in the ocean, your ship won't sail.  Problem I think is that the game checks to see if you have beach/ocean nearby to see if you can build a harbor, but then it allows you to build it on ANY available square, not necessarily a beach with contiguous ocean.  BTW, have you tried launching your ship from the parchment map?

I've also had times when the game sees one measly water square (lake? pond?) and allows me to build a harbor.  That doesn't work either.