In the small area you start in there is even a side quest that refers to the Count of Monte Christo. So if you know the story then you might get a clue on how to solve this somewhat hidden quest.
For the people who don't know it : The Count of Monte-Christo is a novel written in 1846 by a great french writer Alexandre Dumas.
It is a very good book.