I had no such problems with my test of Nav4All on my N95-1. Neither does a friend of mine have problems with it on his SE w800i (with a bluetooth gps). And he is a regular user. Nav4All is designed for minimum bandwidth, as such the maps are *^%*. Still navigation works well, it nicely beeps when exceeding the speedlimit over a set margin, boohoo Nokia Maps, and it gets you where you wanna go. It also nicely access the adresses from my phonebook. Nothing to type in.
Admittedly my test of Nav4All was last year on a GPRS datalink. But I see no reason why 3G should balk.