Eltaire -- If I read things correctly, the problem is that the quest "My little chocobo" doesn't even appear in the first place. Thus the chocobo porter in their town won't have the option to hand over the certificate.