Did you get a reaction from the star stones both times? If you buy / pickpocket the one at the clinic, you would need a companion to use it.
Honestly, it's been too long and my memories are clouded with other playthroughs to remember precisely. I suppose one of the drawbacks to playing since the alpha is I tend to go quickly over the first parts with which I'm familiar and could have missed a slight change to the quest line.
Regardless, I do think a better solution would be to have the companions return to the place where you picked them until the Hall of Heroes is unlocked. After all, how did they get there if the teleporter supposedly doesn't work yet?
