I started it up and replayed the first part every different way I could to determine the required actions and their order. Here's how it looks. Before sparring with Cala at the colosseum, all these conditions must be met:
-Talked to shopkeeper before leaving town.
-Talked to Alfa at town gate and fought six battles outside of town (you automatically leave town after meeting Alfa and are not allowed back until six battles are fought, so this is essentially one thing.)
-Talked to shopkeeper again after returning to town.
-Talked to Cala at castle gate.
-Talked to Julietta in her room.
-Visited church once.
-Visited colosseum once.
You have to talk to the shopkeeper before it's possible to meet Alfa and leave town, you need to fight the six battles and return to town before it's possible to talk to the shopkeeper again, and naturally you run into Cala at the castle gate before you reach Julietta, but other than that, you can do those things in any order. It seems you do have to visit the empty colosseum at least once either way, because I tried doing everything else first and leaving my first visit to the colosseum until the end, entered to find nobody there, then immediately re-entered and Cala was there all of a sudden.
Hope that helps. If by some weird bug she's still not showing up after you've checked everything off, try restarting the game and doing it all again. It only takes a few minutes if you skip any exploring on the side. For instance, it's not necessary to go to the throne room or anywhere too far on the world map.
