I’m stuck in Venezia and can’t catch a ship to the next place I need to go. I’ve done all the things with the couple that you have to get together in order to proceed, but apparently there’s something else I need to do to be able to board the ship.
Firstly, you don’t need to do anything with the couple, was it Nancy and someone? Anyway if you never talked to them, it wouldn’t affect much.
It sounds like you want to head to Demitel’s isle, or Undine’s cave. Or possible even Thor.
If Demitel, talk to everyone in the mayor’s house.
If Undine, then you should’ve talked to everyone in Alvanistia’s research base about where spirits live.
If Thor, that I forget.
You absolutely do have to finish the Nancy/Edwin quest to continue. Certain options don’t open up if you don’t. Check the walkthrough on the shrine; there should be a hint somewhere in there. 
Ah, finally figured out what I was missing. The way to get onto the boat on the left is from the north part of town, like the shrine says, but I couldn’t find that since the way to get there is very narrow. See, I know what I needed, I just needed slightly more detail, because I’m a bit thick some times.