Auto Timezone doesn't update

For Ubuntu 18.04+ make sure Settings -> Privacy -> Location Services is set to "On."

I seem to have fixed this issue by installing gnome-clocks which might serve as the hook gnome-shell uses to get the location data for the time-zone.