Push Notifications aren't working on my android?

[AbsolutZero]

First thing: reboot the phone. There could be an erroneous internet connection issue that'll restore itself when booted again.

Second thing: attempt to uninstall and re-install the applications. Something might've broken from within the apps and a re-install could fix them.

Third thing: If you're that concerned about it, factory reset...although it's not recommended for such a simple problem.

Fourth thing: if you're rooted, try flashing a different ROM

Fifth thing: get used to not having push notifications.