the notification to update comes from our server, when we know there's a newer version. the new version needs to download from the google servers, and your phone has out of date information about what the latest version is, and for some reason it stays out of date for quite a while (several hours).
if it happens during the night, it might automatically download the latest by morning, but that's not usually the case. rebooting your phone solves this.