Using Xara Photo & Graphic Designer 9, which has a built in image vectorizer, and tried it on your map sample. One problem is that your map sample is 72 dpi and your image is small, which gives me little to work with in hopes of creating an adequate conversion. I tried it, and to my judgment the process failed. It did vectorize, but the final image was very blurry and jaggy. I'm sure that if you posted a 300 ppi version of your map file closer to its original size, the conversion would have had better results.
I also sometimes work with CAD in my graphics shop, and I do own a rather expensive raster to vector converter for CAD purposes. It works well for CAD related work, but not well for illustrative work - and it costs more than $1000 for the software - so it is not a solution!
I know someone who works in a CAD shop and spends all his days using a drawing puck (CAD device) to retrace all the linework in existing drawings - including topographical maps like you've posted. Its all very tedious, but he is paid just to do that all day long.
So at best the process is problematic. As stated, if you had higher resolution and larger dimension maps to start with, you'd probably have better luck. As I didn't have much luck trying it with your sample.