I was having this issue as well, it turns out that for some reason my private key didn't match the one associated with the aps_developer_identity.cer I had...
I ended up clearing all of my public and private keys from my 'login' keychain item, then I started the entire process over again (Generated the request)...I submitted the new request file on the program portal and generated a new certificate, downloaded, and installed it by double-clicking it (developer_identity.cer). Then, I reset the provisioning profiles to use the new Push SSL certs, downloaded those, and installed them by double-clicking (aps_developer_identity.cer). Finally, I reset the provisioning profile and downloaded the new one. I cleared out the old one in the Xcode Organizer, and installed the new one. Finally, I exported my 'private' key as key.p12 and my aps_developer_identity.cer as apsdi.p12, and ran the following commands against them:
openssl pkcs12 -clcerts -nokeys -out apsdi.pem -in apsdi.p12
openssl pkcs12 -nocerts -out key.pem -in key.p12
If you're okay using a passphrase (recommended for production):
cat apsdi.pem key.pem > cert.pem
If you wish to use a 'blank' passphrase, you'll need to unencrypt your private key first, using the password you specified when you converted it to pem format:
openssl rsa -in key.pem -out key.unencrypted.pem
And then cat the cert and unencrypted key into apns.pem (or whatever filename you have chosen):
cat apsdi.pem key.unencrypted.pem > apns.pem
It's very important that you export your aps_developer_identity certificate, not your developer_identity certificate as apsdi.pem.
*If you can expand your developer_identity.cer and aps_developer_identity.cer entries in Keychain Access, and you see a 'private' key when you do, everything should work.*