Invalid Signature Error when I update in app store

I had the exact same problem and tried your potential solutions and many others. After a few hours and a night of thinking I stumbled upon something that worked.

My initial application was submitted prior to the final release of the iPhone 2.0 OS. Like you found, subsequent attempts to submit an updated application using the same distribution settings resulted in the error you described. After re-reading Apple's distribution documentation I noticed a new emphasis on wild-carded APP IDs. This emphasis did not exist when I first submitted my application so I did not use a wild-carded APP ID. So, I created a new APP ID with nothing more than an asterisk for the bundle identifier. I then created a new distribution provisioning profile for this APP ID and used it to sign my updated application and it worked! The upload was then accepted through iTunesConnect.

A few things to note:
1. Although you change the bundle identifier of your APP ID, you probably do not want to change the bundle identifier in your application's plist file. Although I don't know for sure, I'm guessing that it may be interpreted as a different application if the plist's bundle identifier changes.
2. When I say it worked I'm only referring to getting the binary upload to succeed. My application is still in review so I can't promise that something else won't crop up.
3. I am certainly no authority on this subject. Hopefully what has worked for me will work for you too.

As reference, you may be interested in reading pages 17 and 37 (assuming the document isn't updated) of the iPhone Developer Program User Guide. They talk a little bit about the wild-carded APP IDs.