Edit: Not a bug! 
If I had bothered to scroll down a little more, or paid attention to the icon more closely, I would have seen that the Kokythiad was leading 5 non-flying units. Duh. Sorry!
Unit #1477 Kokythiad is amphibious and stealthy. I gave a Kokythiad in a coastal (land) castle a pair of winged shoes. The Kokythiad's possible movement did not change at all. The "Flight" icon appears on the Kokythiad view unit screen, but the Kokythiad does not get any overland flight.
The castle the Kokythiad is located in is friendly and not sieged.
Specifically, the Kokythiad is unable to fly over any enemy land territory. The Kokythiad is even unable to fly over 2 consecutive friendly land provinces into a 3rd friendly land province. If I give the winged boots to a Commander (Unit#34) instead, he can fly to any land province within 3 moves.