I don't know a program offhand that will automatically generate the full set of towns, roads, labels, etc.

There are lots of programs that will generate a base map image (http://www.ridgenet.net/~jslayton/software.html has such a package, for example, with a fair number of tutorials hereabouts) and it's pretty straightforward to generate such a map using the noise functions built into most drawing packages. The software mentioned can also generate basic vector contour output for use in third-party packages such as Inkscape if you're more of a vector-type person.