I remember another Aussie user having the same problem after "upgrading" (ha!) to KK, don't know if he found a fix.
I'm still on JB, but have you tried Top NTP? It's on the playstore, there's a free and a donate version (can't link to it from my work pc). It changes the GPS config and is the first app I install on every device I've had - never let me down, instant fix. Worth a try?