I implemented something like this a while back using PHP/Oracle 8i and have been thinking of porting it to PHP/MySQL and creating an open source project for some time.
The difference in my project was that I did not use zip codes because I had to do distance calculations for every city in the entire world (about 2.5 million if you're curious). I don't know the exact source of the data for the non-US cities because my employer had it on a cd, but I obtained the US city information from the U.S. Geological Survey (www.usgs.gov). You can find the files at:
http://mapping.usgs.gov/www/gnis/gnisftp.html
The file that will probably be of most interest is "Pop_places_deci.gz" as this only has cities whereas the other data has every single geographic feature they have mapped (and not too many people are trying to find out how far they are from something like "rock 652"). The only drawback is that this data doesn't have zip codes and I haven't come across a convenient way to merge zip code data with the USGS data. If anyone has suggestions on that I'd like to hear them.
In addition, if you'd like to save yourself the trouble of downloading and parsing through the USGS data sets to build your database I have a MySQL data dump of a city/state/country table schema with all the data from the "Pop_places_deci.gz". I believe I also converted the data into XML format, too. I can make both of these available if there is interest. Also, I already have a number of functions that interact with this data for distance calculations, soundex matches, etc.
If there is enough interest in this topic we could open up a project on SourceForge or something like that. Let me know if anyone is interested in grabbing the data dumps or XML. As I said, I will need to do a bit of work to port some of the distance functions from Oracle but this is something I have been meaning to do for a while anyway.