How to fix Google Play Store Update Error in Android 4.0.4?
Since this app is a Google native app which handles its own updates by itself, maybe the update went wrong. At the moment you could clear its cache, data (you will have to reenter the credentials later again and configure the playstore including notifications and update handling), or uninstall the updates, so it will go to the initial version (can be done by going in Settings -> Applications -> All -> Google Play Store). It should update later automatically.

In case you have a rooted phone, make sure you haven't done any changes in the system lately, or other apps are not interfering (any "freezers", "killers", or similar ones). Also, check if you haven't forbidden mobile network access (Settings -> Data usage, there you can click each app and check/uncheck "Restrict background data"), but even if this was checked, it should work on WiFi.