I don't see anything obvious in the code-signing dump, so that makes me wonder about the production certificate, the app ID and the embedded profile. I assume you've confirmed that the bundle ID for the app in iTunes Connect is set to com.theapp.com (which is a pretty odd identifier if that's not just dummy text). If you haven't done that, check it, but I don't think you'd get past client-side verification if it was wrong.
Now right-click the app bundle you created, view contents and find the embedded.mobileprovisioningprofile. Open it in TextEdit or the like and make sure it's really an App Store profile, not an Ad Hoc one that lists device IDs.
Barring any of those issues, I'd suggest the following.
On the iOS portal, delete and recreate your production certificate (make sure it's the production one), then update the related provisioning profiles to use that. They should show as invalid until you update them.
After that, go to the Xcode Organizer, and delete the provisioning profile you're currently using.
Now, download and install both the new production certificate (download and double-click it) and the new provisioning profile (download and drag it to the Xcode icon).
Update your build settings so the target uses the new certificate and provisioning profile. (I'd delete the old values before selecting the new ones because I've seen Xcode get confused.)
Hold down the option key and select Clean ("Clean All") from the Product menu.
Then build and submit again. You should get asked to use the new cert from your keychain.
That's pretty much a complete flush of the code-signing bits, so it should fix any problems you're having.