Restored our iPhone/iPod Touch devices by erasing everything and reinstalling the OS. Did not sync the device or restore old data to avoid putting in the provisioning profiles again.
Deleted all certificates and private keys from keychain on the mac (all including the Apple provider certificates)
Removed all provisioning profiles from xcode.
From the developer portal, we deleted the adhoc and dev provisioning profiles
From the developer portal, we revoked the push SSL certificates for both dev and production versions
Then we regenerated the push SSL certificates, both production and dev. Note that we did not download them from the wizard itself at this time.
We then waited for a few minutes (5-10 mins) and then generated the provisioning profile. Not downloaded yet.
We again waited a few minutes (5-10 mins) and then downloaded the certificates (sandbox and production) and the profiles (dev and adhoc)
We then generated the single PEM file from the certificates and the key only for the production version. We did not even install the sandbox version certificates in our keychain.
Then installed the adhoc provisioning profile in xcode and the device
Started the application and tested a push notification
It worked.