For me, None of the above solutions worked. I was migrating from two older mac's to a new mac, trying to get release/debug profiles working on Xcode WITHOUT Xcode auto managing them.
The solution for me was that when I went and created the two new Certificates, i ALSO had to go into my provisioning profiles, and add (under both the distribution and dev) the new certificates to the provisioning profiles so recognized them. After doing this & downloading, xcode removed all errors and it is good to go.
Hope this helps someone!