I had a similar situation: multiple developers using the same private key, but I couldn't find mine anymore after upgrade to Lion. The very simple fix was to export the private key for the specific certificate (in my case the Development cert) from the other machine, move it to my computer and drag it into keychain access there. Xcode immediately picked it up and I was good to go.