I got this problem 2 days ago, exactly same as it being described at Stackoverflow. My environment: Xcode 3.1.4, iPhone OS 3.1.2, Mac OS 10.5.8 (yeah, I am a little old school).
Struggled a bit, tried creating new certificates, using old certificates, blah blah blah. Nothing, still see the same message after I added the provision (downloaded from iOS dev center) to Xcode: “A valid signing identity matching this profile could not be found in your keychain”
I read that Stackoverflow carefully, also looked at the Apple Offical Q&A 1688. Finally I figured it out: I need to download the dev certificate approved (automatically) at iOS dev/provision center, double click it (to install on Keychain). It initially complained about “two certificates using same name” or something like that. I deleted the old dev certificate in Keychain. After that I fixed the provision for my apps, and download the relevant provisions, then drop those to Xcode => Organizer. I no longer see the error. Subsequent build and install worked beautifully.
A small battle was won.