This paper introduces the Fourier Space Time-Stepping algorithm to the valuation of variable annuity (VA) contracts embedded with guaranteed minimum withdrawal benefit (GMWB) riders when the underlying fund dynamics evolve under the influence of a regime-switching model. Mortality risk is introduced to the valuation framework by incorporating a two-factor affine stochastic mortality model proposed in Blackburn and Sherris (2013). The paper considers both, static and dynamic policyholder withdrawal behaviour associated with GMWB riders and assesses how model parameters influence the fees levied on providing such guarantees. Our numerical experiments reveal that the GMWB fees are very sensitive to regime-switching parameters; a percentage increase in the force of interest results in significant decrease in guarantee fees. The guarantee fees increase substantially with increasing volatility levels. Numerical experiments also highlight an increasing importance of mortality as maturity of the VA contract increases. Mortality has less impact on shorter maturity contracts regardless of the policyholder's withdrawal behaviour. As much as mortality influences pricing results for long maturities, the associated guarantee fees are decreasing functions of maturities for the VA contracts. Robustness checks of the Fourier Space Time-Stepping algorithm are performed by making numerical comparisons with several existing valuation approaches.