I haven't had this problem since 1.2 but the way of getting back to sea that worked most reliably pre patch is:
Alt + right click in the sea next to your fleet.
This sets up a way point there from your nearest port.
You should now be able to move the fleet onto the waypoint.
Fleet is at sea.