I talked to Licia at the Tower of Flames. Then I returned to Majula and went down the stairs, but she's not there or at the tower. Where is she?
The only places where you can find Licia of Lindeldt are in Heide's Tower of Flames or in the way between Heide's Tower of Flame and Majula, the only way known for her not to be there is after she's killed (Either you invade her with the Crushed Eye Orb or simply kill her). After she's killed a tombstone MIGHT appear, as far as I know there are certain faith requirements for the tombstone to appear (in the same place where she was standing between Majula and Heide's Tower.
A link to the complete information here.