Invalid iPhone Application Binary

I'm trying to upload an application to the iPhone App Store, but I get this error message from iTunes Connect:

The binary you uploaded was invalid. The signature was invalid, or it was not signed with an Apple submission certificate.

Note: The details of original question have been removed, as this page has turned into a repository for all information about possible causes of that particular error message.

For general information on submitting iPhone applications to the App Store, see Steps to upload an iPhone application to the AppStore.

Solution 1:

It's been my experience that Xcode occasionally gets confused about which signing certificate to use. I got into the habit of quitting and restarting Xcode after any change to the code signing settings (and doing a clean build) to work around this problem.

Solution 2:

I just wanted to mention that I too had the problem with zip from the command line as well. The problem lies in the way it handles symlinks by default. Using:

zip -y -r myapp.zip myapp.app

Solved that problem.