There are many small details. I think that it will help you better to understand how the push key is created.
When you choose the Create Push Keystore option the IDE takes two files:
1. aps_xxx.cer - The APN SSL certificate file
2. B4i.p12 - The private key that was created for you when you created the private sign key.
You must use the same certSigningRequest.csr when you create all the certificates or it will not work.
Tried on both my laptop and desktop with the same results, running 4.4 and 4.8
If I re-create my signing key, and then the certificates and provisioning files. I will presumably have to re-submit a new version of the app signed with the new keys to get this to work.
What impact will this have on my other live published apps?