The dreaded binary error has bitten me…
“The binary you uploaded was invalid. The signature was invalid, or it was not signed with an Apple submission certificate.”
Okay, in one case, it was actually valid, as I had been using an icon file that wasn’t named Icon.png and wasn’t 57×57. Thanks to Sean for helping me with that.
But today, it was totally bogus. I made a trivial change for a resubmit of my PrivateWeb app, and the binary was rejected. Clean the project & rebuild, still hosed. Restart XCode, still hosed. Go to the finder and remove every folder from my project’s build directory and then build again – and it WORKED??? WTF?!
Ahem. I’m glad it worked, but seriously… There’s something buggy in XCode land.

It appears that deleting the build directory is perfectly safe. So I never commit the build directory to source control at all, and when saving the project directory (by Compressing it) I always delete the build directory first. It’s much better than just doing a “clean” in Xcode.
I’m having this same problem. I’ll be trying your solution tonight but all I did was change the application name and rebuild it and I got that error. This will be the second frustrating bug I’ve experienced in xcode myself.