Turn your mind back to Disney's Fantasia 2000, The second segment. A wonderful piece of music called "The Pines of Rome" with an animation of humpback whales that jump out of the water and fly up into the clouds. this would provide you with large animals that could carry people and fly from floating island to floating island.
Okay, this is far-fetched so lets look at how they got up there.
Assume that the planet surface below is mostly covered in water. The islands hover at varying altitudes above the surface. What makes the Islands hover? The oceans contain large quantities of handwavium, which is also the principle component of the floating islands. The islands rise and fall slowly and majestically, and when they touch down in the ocean lots of little krill gorge themselves on the handwavium rich strata on the underside of the islands. The whales eat the krill, and for a while they gain the power of flight. Swarms of insects in the air also serve as handwavium rich snacks for the whales, prolonging their ability to fly. The whales return to the oceans for mating and caring for their young.
Gaining flight via diet is kind of like how Flamingos are pink because of the shrimp they eat.
The whales look a lot like humpbacks but have additional limbs as wings for control in flight, but that fold back flat against the body for movement in water. Propulsion is by means of a series of bladders that act as both lungs and like an octopus jet. Inhale through the nose, exhale out the other end. Not real fast, but majestic.
I know I left out the ability for land locomotion, but only because I like the idea of flying whales. If land locomotion is absolutely required, I guess you could use giant Sea Otters with feathers and wings. Use the same food cycle mechanism, but since otters are carnivorous, they could eat more normal birds in addition to the fish that eat the krill that contain the handwavium.
As mentioned by Will, Pegasus, gryphon, dragon, etc all have been done to death I like the idea of doing things a little differently