The succubus's non-magical movement modes are replaced by the movement modes of whatever she turns into.
The succubus's flight is a movement mode. It's in the "Speed" section, not the "Special Qualities" section of the stat block, so it's not magical or anything special like that.
Now, when a succubus uses her Change Shape supernatural ability, it's got some very specific rules to follow, including:
- The creature loses the natural weapons and movement modes of its original form, as well as any extraordinary special attacks of its original form not derived from class levels (such as the barbarian’s rage class feature).
- The creature gains the natural weapons, movement modes, and extraordinary special attacks of its new form.
So the succubus loses her own flight speed (as well as her land speed!) and replaces it with whatever movement modes her new form might have. She can only fly when using Change Shape if her new shape can itself fly.
(Aside: polymorph-type abilities of any kind have a long, tortured history in D&D 3.5 and its companions. E.g., different forms of shapechange effects have different rules about what you keep from your original form and what you get from the new one, so you have to look up the details every time. There are many different homebrew and optional-variant implementations of the shapechanging rules; you may want to look into them if the SRD ruleset doesn't satisfy.)