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!