Did you forget to pick up the quest? The only other message I've seen is the one that tells you to wait a little while longer, because someone else has just caught it or you just *** up and let it get away.
I definitely had picked up the quest. I have given up using that Chocobo Spoor point and have started using the one near the Amuckatrice instead, i've not had the same message at that one.