Does it have to be an enchantment? I'd make it a feat.
Generalized Fast Movement
Prereq: fast movement class feature
Pick one movement mode you have a speed for in which you do not already have fast movement. Your fast movement class bonus also applies to this movement mode.
Special: This feat may be taken more than once. The effects do not stack. Each time you take it, it applies to a new movement mode you have a speed for.
So he takes Generalized Fast Movement (fly) to boost his fly speed; if (and only if) he gets a swim speed sometime he could also take Generalized Fast Movement (swim). Ditto climb, burrow, whatever. One feat per movement mode seems right to me.
What do you mean with "mobility issues"? And what kind of fly speed does he have (the template grants twice the base land speed as fly speed, which should be 60ft)?
Is there no source of Haste or Blessing of Fervor aviable? Boots of Speed, when in doubt (as the boot slots aren't needed to gain flying or dealing with difficult terrain). These grant a 30ft bonus to all movement speeds.
Draconomicon had the Improved Speed feat if you don't mind importing something from 3.5.
There was also the Fly Like an Arrow spell from a Dragon magazine.