It looks like there are several different issues that can cause this. Mine was similar to JosephH's, but not the same.
For me there was another provisioning profile that was valid, but from a different user. I have several apple accounts that I am a member of for development.
My build was using a different profile from another user account when it went to sign. This was even though I had told it which one to use in the settings.
I solved this by having to delete that other provisioning profile whenever I wanted to build this app for testflight. The provisioning profile would always come back if I did an update from the dev site for that other user account.
The final solution was that I happened to get a new mac for development and didn't install that other user account's profiles into this mac yet. Now everything builds fine without doing anything.