Like you, Kapeman, I am also determined to use harbours and ships and I have built harbours in every game as soon as a city reaches level three. As you have discovered, they are a little quirky. You need to have a full beach tile (all four sides) adjacent to one of the city buildings on one side and touching the water on the opposite side. You can have a small fraction of a tile along any of the sides of the full tile - that's okay, but a grouping of partial tiles won't work. With this in mind, sometimes you may need to cast the erosion spell more than once.The key is having one full contiguous tile, otherwise you won't get a harbour. Be persistent and keep trying. Once you get the hang of it, you will be able to build harbours for any city close to water. They are a missed opportunity for most players (blank stares all around)who don't realize how useful harbours can be with the Fish Market mod. Fairly early in the game you can double your Kingdom's food production which is a huge boost. Also boats are great for exploring and scouting since they cannot be attacked. I have often found special resources this way which led to an early win even at higher difficulties. It's too bad that their movement is so gimped. If they had slightly greater movement they would also be good for transporting troops!

are they cliff tiles your trying to cast it on? if that isn't working I'd wait and go straight for destroy land spell.