I've got an app that we've submitted dozends of versions to in the last 6 months and we do use APNS. I got the following email from Apple after upgrading to Xcode 8
We have discovered one or more issues with your recent delivery for
APP_NAME. Your delivery was
successful, but you may wish to correct the following issues in your
Missing Push Notification Entitlement - Your app includes an API for
Apple's Push Notification service, but the aps-environment entitlement
is missing from the app's signature. To resolve this, make sure your
App ID is enabled for push notification in the Provisioning Portal.
Then, sign your app with a distribution provisioning profile that
includes the aps-environment entitlement. This will create the correct
signature, and you can resubmit your app. See "Provisioning and
Development" in the Local and Push Notification Programming Guide for
more information. If your app does not use the Apple Push Notification
service, no action is required. You may remove the API from future
submissions to stop this warning. If you use a third-party framework,
you may need to contact the developer for information on removing the
After you’ve corrected the issues, you can use Xcode or Application
Loader to upload a new binary to iTunes Connect.
The App Store team
Very easy actually. For some reason it got disabled on Xcode 8 but go to Targets -> Capabilities and verify Push Notifications is all correct on that view. For me it had a "Fix Me" I had to click, and voila.