Gremlion: All alliance quests are broken since first beta.
edit: or maybe better to say that they were broken since first beta and nobody ever mentioned that they were fixed...
There's a workaround untill they get around to fixing the alliance quests -
They will finish properly if the hero has no other quests in his log. So complete or just delete all other UNFINISHED quests he has (crystal, Temple of Light, unfinished copies of the alliance quest, whatever), and the alliance should trigger once you negotiate with the questgiver.
Confirmed with lizardmen and elves.
EDIT: And goblins.