Check if there are any hints told by the fortuneteller or the barkeeper.
Try having Cindy take Faylen, by becoming her and visiting the Treasure cave. After that, visit the desert palace as Celica.
