I've been having this problem since Xcode 7.1 (for more than a month). I did everything I could trying to solve this: restart Xcode, clean project, clean build folder, build with a device connected, reinstall Xcode multiple times, even formatting the whole disk and starting from scratch. None of this worked.
During this time my colleague was always able to upload the very same builds to App Store without any problem.
Curiously, what solved this problem for me was disconnecting my non-Apple wireless mouse.
I found this out when I tried to submit an app from my home computer and got the same error. I disconnected the mouse dongle, tried again and it went through.
I've verified this three times both on my home (MacBook Pro 2013) and work computer (Mac Mini 2014).
This leads me to believe that during the app submission process Apple may check if your environment is purely made by Apple or not, and may block your submission based on that. This would explain the "Cannot verify client" message.