I've only done a lost animal quest once, so I am in no way an expert. However I can think of 3.5 things that may have gone wrong, or needed to be done:
1. Is it really the last track?
2. Did you use the right material for the fire?
3. Did you wait?
The third one is important. I lit the fire, watched it burn out, and nothing happened. I waited a few minutes and then suddenly I saw the animal walking towards me.
And now for the .5. Is your character a jerk? I remember the shaman saying you had to have a good heart or something... not sure if that can really effect it.