Google (and other western maps) do not show the right location because china forces them to add random deviation. I use 3rd party program (locus) and download google maps of the area where I want to go (e.g. shanghai or most of it anyway since accurate and large area makes a big file), or just use 3g if you have. Then use programs function to de-offset the deviation, this works locally since the deviation is not the same everywhere. Another option is to use vector maps like openstreetmap which work out of the box but are not detailed. Have not tried navigation.

This does not answer OP's question though and I am interested to know as well if any stand-alone navigators are good (and in english) or maybe there is a good program for android?

e: and is it true that possessing some of the maps is illegal in china?