I had this problem after I created a new developer certificate.
The following was already correct: The old private key was deleted from the keychain, all profiles where up to date, the build configuration and signing settings were correct. Yet I had this problem.
Solution: I had to restart Xcode (5.1.1), because it was not aware of my new developer certificate. I also deleted the obsolete profiles from my devices just to be sure and to clean up.