OK, I've read every single topic on SO about this problem and I am still have no solution.
Our app was signed for distribution and was in itunesconnect at "Waiting for review", but we found some bugs and rejected it.
After couple of days we were ready to re-submit the app and "Application failed codesign verification. The signature was invalid, or it was not signed..." occured.
We done next steps:
Didn't want to do it (accept own answer) - but in my case the reason of error was in files named like ._picname.png in folders added to the project as links to folders (blue in Xcode). After these files have been removed the app was succesfully uploaded to Apple Appstore.