In a previous paper (Maoz et al. 1999), we reported a Hubble Space Telescope (HST) Cepheid distance to the galaxy NGC 4258 obtained using the calibrations and methods then standard for the Key Project on the Extragalactic Distance Scale. Here, we reevaluate the Cepheid distance using the revised Key Project procedures described in Freedman et al. (2001). These revisions alter the zero points and slopes of the Cepheid Period-Luminosity (P-L) relations derived at the Large Magellanic Cloud (LMC), the calibration of the HST WFPC2 camera, and the treatment of metallicity differences. We also provide herein full information on the Cepheids described in Maoz et al. 1999. Using the refined Key Project techniques and calibrations, we determine the distance modulus of NGC 4258 to be 29.47 +/- 0.09 mag (unique to this determination) +/- 0.15 mag (systematic uncertainties in Key Project distances), corresponding to a metric distance of 7.8 +/- 0.3 +/- 0.5 Mpc and 1.2 sigma from the maser distance of 7.2 +/- 0.5 Mpc. We also test the alternative Cepheid P-L relations of Feast (1999), which yield more discrepant results. Additionally, we place weak limits upon the distance to the LMC and upon the effect of metallicity in Cepheid distance determinations.

26 pages in emulateapj5 format, including 6 figures and 5 tables. Accepted for publication in the Astrophysical Journal