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.