No GPS Fix After Shipping Vehicle to Oz

[BabyMakingWeather]

Here's one for the Nav gurus...

Shipped my vehicle from the UK to Australia, and am now having problems getting a fix with Nav.

I've inserted the latest BMW map CD for Australia (v13), which was accepted no problem. However although the streets are searchable, and it's also possible to enter a destination, the GPS is not fixing my location. Instead it's showing me in the Pacific Ocean about 40km offshore! The car has been on for at least 2 hours, so the Nav's had plenty time to think about it. The gyro compass is working though, as the map is orientating correctly with the direction of travel.

If I enter the diagnostics menu, the status of the GPS is "Searching", with no satellites visible.

So what's gone wrong here - my other GPS's work fine in both countries, so why not the BMW Siemans/VDO too?

Do I have to take the car to a dealer to have something about the Nav recoded for Australia, or do I have bigger problems? It's a MKIV.

Thanks in advance