PushSharp APNS production: The credentials supplied to the package were not recognized (development works fine though)

My app just got ready for sale on App Store, but none of my production devices (devices that have installed the app from App Store) are getting push notifications. When I try to send a push notification to a production device, I am getting this error:

"The credentials supplied to the package were not recognized" 
(System.ComponentModel.Win32Exception)

This exception is internally thrown and caught in an infinite loop:

It is thrown at line 539 of ApplePushChannel.cs file:

    try
{
    stream.AuthenticateAsClient(this.appleSettings.Host, this.certificates, 
        System.Security.Authentication.SslProtocols.Ssl3, false);
    //stream.AuthenticateAsClient(this.appleSettings.Host);
}
catch (System.Security.Authentication.AuthenticationException ex)
{
    throw new ConnectionFailureException("SSL Stream Failed to Authenticate as Client", ex);
}

This is the output of the application in Visual Studio Output:

...
A first chance exception of type 'System.ComponentModel.Win32Exception' occurred in System.dll
A first chance exception of type 'System.ObjectDisposedException' occurred in System.dll
A first chance exception of type 'System.ComponentModel.Win32Exception' occurred in System.dll
A first chance exception of type 'System.ObjectDisposedException' occurred in System.dll
A first chance exception of type 'System.ComponentModel.Win32Exception' occurred in System.dll
A first chance exception of type 'System.ObjectDisposedException' occurred in System.dll
A first chance exception of type 'System.ComponentModel.Win32Exception' occurred in System.dll
A first chance exception of type 'System.ObjectDisposedException' occurred in System.dll
A first chance exception of type 'System.ComponentModel.Win32Exception' occurred in System.dll
...(it keeps getting thrown until I stop it manually)

Here are the things I've tried:

• Double checked that the device ID I'm trying is registered with a production device token.
• Revoked and regenerated the APNS Production certificate, exported it with the private key to a new .p12 file, and tried again with the new certificate. (I had the same problem with development push notifications, and this solved my problem)
• Changed the SSL protocol from Ssl3 to Tls. (a few days ago there was a problem with protocol version, and it fixed a problem temporarily. There shouldn't be need for this, but the error I'm getting is the same as the one I was getting before which this fixed)
• Checked that I'm actually trying to connect to production server with the production certificate instead of development server/certificate.
• Checked that I can access the APNS server directly (my ASP.NET app lives inside a Parallels VM Windows 8.1 at my Mac, here is the output from my Mac, just to avoid confusion:

(Terminal output) Edit: I was pinging the sandbox server, I've pinged the production server, I verify that I can connect to it too, so it's not the issue.

can$ sudo nmap -p 2195 gateway.sandbox.push.apple.com
Starting Nmap 6.40-2 ( http://nmap.org ) at 2014-04-28 00:06 EEST
Nmap scan report for gateway.sandbox.push.apple.com (17.149.34.189)
Host is up (0.49s latency).
Other addresses for gateway.sandbox.push.apple.com (not scanned): 17.149.34.187 17.149.34.188
PORT     STATE SERVICE
2195/tcp open  unknown

Why would PushSharp not negotiate with APNS servers?

I figured out the problem. I revoked and regenerated the certificate again, and this time I only exported the private key (without the certificate). In Keychain access, I exported as .p12 and used the new file and it worked. For some reason, PushSharp wasn't play well with .p12 when both certificate and private key are present in the file.