Just changed my address also, it took it OK. Now have my local UK weather when asking "Alexa, what is the weather". Cool :-)
Bought mine in the States. I'm there for 5 months (Snowbird) so I don't want to change my American address. (I'd lose some functionality with my American Prime membership if I did so).
For Canadian weather in my home town of Mississauga, I merely say:
"Alexa, what is the weather *in Mississauga?* Works every time.