Xcode "The private key for is not installed on this mac - distributing"

Try following these steps:

1. Revoke your existing iOS Distribution Certificate from the iOS developer website.
2. Generate a new iOS Distribution Certificate by going to XCode Preferences->Accounts->View Details and then clicking the + underneath the list of signing identities.
3. Go back to the developer website and make sure all your provisioning profiles are configured with the new certificate. (They should all be listed as Active when you are done.)
4. Go back to XCode and refresh your list of provisioning profiles.

I had the same issue as you did and this resolved it just fine.

This solved it for me without starting all the way from scratch:
1. Open Keychain Access on the machine that was used to generate the private keys
2. Select Keychains->Login and Category->Certificates on the left hand side
3. Locate the two certificates iPhone Developer: [your developer name] and iPhone Distribution: [your developer name]
4. Select both, right click and choose Export 2 items...
5. Enter a password of choice, save to disk and get the .p12-file over to the other machine that won't sign
6. Open the file, enter the password and you should be good to go.

Having a similar problem, after several days of testing, checking, try to repairing and so on, what worked for me was simply:

1. Open Xcode's preferences (Accounts panel)
2. Click on "Manage Certificates".
3. Add a new certificate.

Then everything started working again.