EDIT: From Altea, sail a bit south and then through a small gab, as far to the west as you can. The tower is inside a piece of land resembling a crescent. Here is an image of the world map, hopefully that will help you (Source: GameFAQs).