This problem is by far the biggest pain I've had with the 2.3.5/ 3.0 update.
The Navigation/ constant prompting to buy a license/ update the maps/ and GPS Searching is insane.
I've done the full factory reset although i didn't want to, but the problem was so bad It had to be done, about 12 hours post reset, it started again.
Locations is basically overiding the phone, everytime the USB Charger or PC USB is plugged in or out the program boots up and takes me to Locations/ Navigations License screen.
Any help would be superb, this phone was absolutely Bomb Proof for over 12 months until this update, Very Disappointing.