As no one has updated or answered this question since Nathan pointed out the original answer link is unavailable (Point number one on posting on stackoverflow "Please be sure to answer the question") here is an answer from my experiance, hope it helps someone:
For this specific question (Dev/Distribution cert installed but no private key) the answer is a choice of 2 alternatives:
1. Create a new certificate identity via the apple devloper portal
In this case you'll need to log into the apple developer portal and use the assistant, as part of this you will need to create and upload a CSR (Certificate Signing Request) which will also create the public and private keys on the machine. Apple sign the request and voila, a signed public/private certificate pair : Reference
2. Export the private key from the machine originally used to create the Certificate
This case is when your signing with an identity previously created, probably on an old machine or if (as in my case) your developing for a client that has their ID's already created. If you can't access the machine originally used to create the certificate identity you'll have to create a new identity as per the guide/assistant.
To do this, you will need to export your private key (a .p12 file), or public/private key pair via Keychain Access, and install the private key or key pair to the machine your developing on. Here's a guide I found on stackoverflow.
Ref: http://iphonedevsdk.com/forum/iphone-sdk-development/11498-problems-exporting-importing-p12-private-key-for-developing-on-another-mac.html
PS> Be warned, I am performing the latter option right now, and while evidence suggests this will work, it is untested by me as of yet, If if doesn't work I will re-reply!
Revoke your current certificate, wait a few seconds and refresh the page and you should see a button "Request Certificate". You'll have to follow the Certificate Signing Request instructions again, and upload the .csr file. You'll then have to wait for your Team Administrator (could well be you) to Accept the new certificate before downloading it and installing in your KeyChain.
You'll have to create a new provisioning profile for the App, using the new certificate.
Hope this helps :)
Best Answer
You can request a new Distribution Certificate on the iPhone Developer Program Portal and then create a new Provisioning Profile for App Store distribution.
This should not create any problems for the distribution process.
Apps uploaded with the old certificate will continue to work and you will be able to release updates for existing apps.