As above - obviously the phone's been flashed with the upgrade, back to factory settings and lost the voice navigation facility. How do I go about getting it re-enabled? I can't be the only one in this position :(
Nokia replied today and for anyone in the same boat, their reply is as follows:
With regard to your email, if you have updated your phone's software during the validity of your navigation license, you can manually update the license by referring to the following steps:
Select Maps > Options > Extra Services > Add navigation.
Choose the region for which you purchased the navigation license and go to 'Options' > 'Update'.
Please allow the connection to the license server to check the purchase & license options by selecting 'Yes' and then by selecting the proper Internet access point (if asked). A note of 'xxx-day license activated' is shown where 'xxx' is the amount of days left of your license or alternatively the mobile device informs you that the license is updated.
Kind regards,
Nokia Care
And it works :)