I managed to make a successful build and upload it to the store.
I had to make a new Identifier on developer.apple.com. The key thing it needed was to have Push Notifications enabled, with a certificate:
I then generated a new Certificate and Profile. For the Profile, I used the new Identity.
Let me know if this works for you!