After upgrading from XCode 7.x to 8.x, while submitting our app to the AppStore, we've encountered the following error:

Missing Push Notification Entitlement - Your app appears to register with the Apple Push Notification service, but the app signature's entitlements do not include the "aps-environment" entitlement. If your app uses the Apple Push Notification service, make sure your App ID is enabled for Push Notification in the Provisioning Portal, and resubmit after signing your app with a Distribution provisioning profile that includes the "aps-environment" entitlement.

Since nothing was changed in regards to our certificates and provisioning profile pairs, we were close to dismissing this as an Apple error.

Lucky we didn't.

Deep inside XCode's release notes, as a known issue, lies this gem:

Xcode 8 does not automatically copy the aps-environment entitlement from provisioning profiles at build time. This behavior is intentional. To use this entitlement, either enable Push Notifications in the project editor’s Capabilities pane, or manually add the entitlement to your entitlements file. (28076333)

TL;DR

In plain English - we need to retell XCode that the app supports Push Notification.
This is easily done by enabling Push Notifications in the project editor’s Capabilities pane: