I have been using the Delorme stuff for quite some time and have the same issue, though running Mepis linux.
I have tried wine, cedega and now Crossover Office, all to no avail, sadly.
A searchable, routing navigation application is the ONLY thing keeping MS on my laptop now, so I am highly motivated to find a solution.
Personally, I would be fine with using something linux-native, as long as map and routing data was available, and I could plug in my destination and be given a route.
The problem seems to be twofold-
lack of perceived market (keeps big companies from bothering)
cost of data and programming (keeps smaller efforts from having a chance)
Since I vastly Street Atlas to the other windows nav. offerings, I am trying to find a solution to running this in linux.
One suggestion I have for anyone in a similar situation is to contact any/all windows nav software producers and ask for linux versions.
Enough requests and they may do something.