Appleのアプリ申請でバイナリアップロードでエラーメールが来る

###前提・実現したいこと
謝罪：
適当なタグ（Apple ストア申請など）が無かった為、iOSという括りで投稿致します。

環境情報：
・Xcode 8
・Mac OS Sierra (10.12)

補足情報：
過去に申請に使用していた端末が壊れてしまい、新しい端末で申請作業を行っております。
申請しようとしているアプリはストアに上げている物のバージョンアップで、Push通知の機能を持っています。
Google検索で良く引っかかる「Push通知を実装していないのに【Missing Push Notification Entitlement】のメールが来る」というのとは状況が異なります。

質問の概要：
Macでアプリの申請に関しての質問です。
ストアにリリースしているアプリのバージョンアップを行うに伴ってアプリの改修と申請をしようとしています。
XcodeでArchive、Validateを終えてストアへのアップロードを行うと
以下のような内容のメールが飛んできます。

###メールの本文(抜粋)
可読性が低かったので多少改行しています。

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 API.

###試したこと
実際に作業した流れを示します。
0. 「App Store and Ad Hoc」のCertificateが切れていた為、作成。(古いものは消していない)
0. Xcodeで Signing(Release) に、1で作成した Certificate の情報を選択。
（端末に複数のApp DevelopperのキーチェーンがあるのでAutomaticにしていません。）
0. バイナリのアップロードし、問題のメールを受信。
0. 問題の Provisioning Profiles の Certificate を1で作成したものに変更。
0. 再度アップロードし、同じメールを受信。
0. 「Apple Push Nortification service SSL」を新規作成。(有効期限の残っているものが有るが、それが原因と思い作成しました。)
0. Production SSL Certificate に1で作成した Certificate の情報を追加。
0. 再度アップロードし、同じメールを受信。
###質問
正直、手詰まりです。
問題のありそうなチェックすべき点を列挙して頂けるとありがたいです。