Everyone i know got a colored chocobo from the eggs the little girl sells in Jeuno. If not in the first, it was in the second try. Looks to me that it's a bit too much based on luck.