NOTE: This process is heavily simplified in XCode 4 (although not personally tested by me) with importing and exporting of developer profiles through the Organizer window (Developer Profile section).
This is how I got it working.
1) Login to the iOS Provisioning Portal as the Agent.
2) Run through the process of making the Distribution Certificate Signing Request / Provisioning Profile: http://developer.apple.com/iphone/manage/distribution/index.action. These instructions a re super long, but pretty clear and necessary.
3) Pay extra attention to the section "Obtaining your iOS Distribution Certificate" > "Saving your Private Key and Transferring to Other Systems" on that page. It describes how to generate and save the Agent's .p12 file.
4) Now invite other developer(s) to be part of the team in the Member Center: https://developer.apple.com/membercenter/index.action#invitations
5) Back in the iOS Provisioning Portal, download the app's Distribution Certificate (Certificates > Distribution (tab)). Should be named "distribution_identity.cer"
6) Now download the Distribution Provisioning Profile (Provisioning > Distribution (tab)). Should be named "whatever_you_named_it.mobileprovision"
7) Email those two files along with the Agent's .p12 file to your other developer machine.
8) On the developer's machine, double-click the distribution_identity.cer file and it should load up in Keychain Access
9) Drag the .p12 file to Keychain and it should automatically put the identity under the certificate
10) Drag the whatever_you_named_it.mobileprovision file into XCode.
11) In each of the Project and Build's Info windows, set the Code Signing Identity to the "iPhone Distribution - Your Company" identity which should now be available.
Hope that helps. Rob
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!
Best Answer
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 :)