Potential explanation: O2 transport in the pulmonary capillaries is normally perfusion-limited, meaning alveolar oxygen tension equals pulmonary blood oxygen tension at the end of the pulmonary capillaries. With increasing FIO2, PAO2 increases such that O2 transport becomes diffusion-limited, meaning the blood oxygen tension < alveolar oxygen tension at the end of the capillaries. The higher the FIO2, the more right-shifted the O2 transport curve becomes, and the greater the difference between PAO2 and PaO2, thus, the greater the A-a gradient.
Edit: Also keep in mind the PaO2 is never exactly equal to PAO2 anyway, due to physiologic shunting (e.g. via the bronchial vasculature), plus of course any pathologic V/Q mismatch or diffusion impairment.