Another cause (verified):
Apple has a major bug in Xcode going back to version 3.x, where it magically overwrites the OS X keychain with a fake keychain from inside Xcode, re-installing certs (and private keys!) that you already deleted
...so, if you have "new cert" installed, and nothing else, Xcode will sometimes get into an infinite loop where it will keep ALSO installing "old cert" (that doesn't exist anywhere except inside XCode!).
...and because of ANOTHER bug in Xcode (unfixed for 3+ years now...), Xcode sometimes automatically selects the "oldest cert I can find" (whcih, by definition, is incorrect - I think someone at Apple got mixed up between "oldest" and "newest" :( )
...and EVEN THOUGH you've selected the correct provisioning profile, Xcode sends the "old" provisioning profile to the device, then signs with the "new" profile, causing this error
Solution: you have to un-FUBAR Xcode's FUBAR of your Keychain.
This is harder than it sounds (there are multiple SO posts on this topic) - it involves multiple reboots of your machine, deleting the key every time.
Eventually, Xcode gives up on corrupting your OS, and accepts the reality you present it with :).