Well, I just got Spore for Christmas... and I know what you mean, but the idea of wings didn't originate from Spore...
Anyway, this would be a good idea. Maybe different kinds- butterfly, bat, and dragon.
They should be datablocks, which are No-Jet, but with the wings on. And maybe add some kinds that run out after a while, so you have to land.
Powerful-- Lasts for a while
Medium-- about 10 flaps and then you have to land
Weak-- about 2 flaps
Infinite-- you can fly forever.