I installed the latest Adobe AIR installer, v1.5. Turns out Adobe AIR changes your default keychain from login to something else, which then completely breaks all Xcode signing.
To resolve this problem, open up Keychain Access, then right-click on the login keychain. Select “Make Keychain ‘login’ default” in the popup menu.
Then go back to iPhone development.