Titanium Backup and similar root-friendly solutions that can restore app data after a custom ROM flash or factory reset are extremely useful, but it turns out that using them may stop apps from sending you push notifications. This is due to a notification backend from Google that most apps use. The way that it's set up means that restoring apps and data may break notifications, and the simplest solution is to just uninstall the backed-up copies and reinstall them from the Play Store.
While many apps that you get from the Play Store have their own push notification system, many simply use the Firebase Cloud Messaging service, a developer service that Google provides. This system issues a unique token to each user upon their download of an app from the Play Store. Naturally, this token is usually restored when using a solution like Titanium Backup. The problem comes when that token goes to the server to retrieve a notification, then comes back looking for its matching token. Your device's new firmware has a fresh token in most cases, while the app is looking for the old token. It will fail to find it, and give up. By downloading such apps from the Play Store again, you're refreshing your app token to match your device token, which should fix any notification issues. It is worth noting that it's the app installation that refreshes the token, so it should be perfectly safe to copy over your data from a backup solution once you've installed apps from the Play Store.
Some phones come without Google Play Services, or users may choose to install a custom ROM without the Google Apps package. Without the Play Store, there can be no token registry on a per-app basis with Firebase Cloud Messaging. In such cases, most apps will just use their own notification setup as a backup measure. While this process can be more intensive to do manually, most modern Android devices will give you the option to automatically reinstall some or all of your apps during the startup process. Naturally, none of this will matter with apps that were obtained outside of the Play Store; they can't use Firebase Cloud Messaging anyway.