Is it necessary to open each app at least once after restoring from an iCloud Backup before Push Notifications will be generated?
So - to answer my own question. It appears that after restoring from an iCloud Backup (I haven't been able to test with iTunes), that you have to open each app that you were previously receiving notifications for before restoring at least once - not performing this step means that they simply arn't generated, even though they're listed as being allowed to send notifications when checking from within Settings.app. I'm not sure why technically this happens - maybe somebody else has further insight which would be useful.