Well, I haven't played for a long time. I was in a city and then suddenly my location chanced all of a sudden. Now I just crossed terrain and when I arrived at my destination I found myself in the ocean not being able to get out. I think it is because I got teleported in my old position and the way I was travelling, crossing terrain, my destination, was where the ocean was. Now I am stuck and get out.
It sounds like the location you where at before you crossed terrain was next to an Ocean. When you crossed the terrain you weren't teleported you just traveled into an ocean. Of course I'm assuming you're on foot.