I got the Assassin Nabaja, went to a quest trigger with her and got the Rats in the Ruins quests. After going to the ruins she got 1 dead rat item. However upon going back to the quest trigger I was informed there were no quests to complete and this quest had already been taken. In order to complete the quest I had to give the rat item to the sovereign and then go to the quest trigger. Only then was I able to complete the quest.
Save showing the behavior. Nabaja has the dead rat in her possession and is standing on the quest trigger in question. Moving her off and back on will show the message. Giving the rat to the sovereign allows the quest to complete.
http://dl.dropbox.com/u/6059389/PreviousAutoSave.EleSav
Incidentally if I try to load this save and then click End Turn, end turn remains greyed out and I cannot continue! This is only occurring when I load the saved game!