If you get the tree-branch from the talking tree in the Dark Forest, the quest will succeed. If you get the branch from Mpenzak (Which I'm guessing you did) then the quest will fail.

"Oh Lord, how long will the search go on?"