Hi Jason ,
Make sure you are completely deleting the old Certs and Provisions that were created before including Push Notifications by deleting them from your KeyChain. I recommend doing a search and making sure they are completely deleted from your system, including deleting your new Certs and Provisions that include Push Notifications.
Once you are sure all remnants of the old Certs and Provisions are removed, re-download the Certs and Provisions that you generated after configuring the app ID for push. Let me know if this does not resolve your issue.
.