While questing in Vash'jir my wife and I on different computers had trouble turning in quests with the little "?" mark in the quest tracker. On certain quests, like the one with the eels, it will say "quest not in the database". This is weird because when cata first came out I quested down there and everything worked perfectly.
Keep in mind it's doing this on 2 separate computers so I don't think it's our computers causing the issue. The only way around this is to close out WoW and start without Carbonite.. turn in the quest then restart WoW, turning Carbonite on in the process.