In a recent paper describing HST observations of Cepheids in the spiral galaxy NGC 4258, Newman et al. (2001) report that the revised calibrations and methods for the Key Project on the Extragalactic Distance Scale yield that the true distance modulus of this galaxy is 29.40+-0.09 mag, corresponding to a metric distance of 7.6+-0.3 Mpc. This Cepheid distance, which holds for 18.50 mag as the true distance modulus of the LMC, is not significantly larger than 7.2+-0.5 Mpc, the value determined by Herrnstein et al. (1999) from purely geometric considerations on the orbital motions of water maser sources. However, if the metallicity difference D[O/H]~0.35 between NGC 4258 and LMC is taken into account, then the Key Project methods lead to a metallicity-corrected value of 29.47+-0.09 mag, with 18.50 mag for the LMC, namely to a Cepheid distance of 7.8+-0.3 Mpc, which is 1.2 sigma from the maser determination. In this paper we show that the metallicity correction on Cepheid distance determinations, as suggested by pulsation models, might provide the natural way of reaching a close agreement between Cepheid and maser distance to NGC 4258 for a wide variety of LMC distance determinations.