You need to feed your Chocobo enough fruit that you get the message "[Chocobo's Name] is beginning to grow new feathers!" Every further appearance of that message will be the chocobo changing to a different color.