Perhaps you are asking the wrong character. Because the bartender has hints for all story quests, and the fortune teller has hints for all personal ones, which are usually hidden.
First, check on the quest list screen to see if all characters have 100% values. Also, the Fortune Teller may not always give advice if Celica is not developing enough as a mage (magic, alchemy, skills, friendship, Nel's training). It's hard to guess, since there are many variables in the game.
