I have got a HTC Titan and a HTC HD7 both in the UK and I have had a weird problem from day one of having the Titan.
Basically upon activating my Titan for the first time, I started the Maps app and in its settings there was an option to read out aloud directions.
Upon planning a route, voice turn by turn started in British English.
However, after exiting Maps and restarting it, there were no more voice instructions! Even the option in Maps settings is gone.
I tried hard resetting and the problem repeats in exactly the same way!
I went back to my HD7 and noticed that it had normal voice navigation but I found that it was also set to English - International in regional settings.
I changed it to English UK and the same situation as my Titan arose!
Are your Windows Phones exhibiting the same problems, especially the Titan ?