be sure that you are generating provisioning profile after adding device, or when you're just renewing profile.
And your provisioning profile must be linked with certificate, that you have in keychain.
(certificate+key)
All devices must be readded on demand, after renewing dev program (!)
In general, It's pretty sraightforward (just try it from the clean sheet, delete all the old stuff)
1) cert signing request
2) appid (if new app, if old just skip, optional - apns stuff)
3) certificates dev/distr (import them)
4) devices
5) provisioning profiles (import them)
in xcode choose in all positions needed profile, sometimes choosing parent option do not change profile for all fields of "Signing Identity" in xcode.
Deleting of old provisioning profiles is optional, it's not a problem when you have many of them
it's only problem when signing identities are more then one, ie: old expired and new one.
(In xcode 5 it will be easier to choose identity)
EDIT: it really seems like in build settings in code signing identity select options (some option) an old profile is chosen, and xcode gives this error.