Update: I finally figured this out. Well, sort of. Here are the steps I took:
1. I deleted all of the provisioning profiles, but this did not seem to help.
2. I checked that the provisioning profiles I eventually used had the correct entitlements using 'security cms -D -i "Payload/YourApp.app/embedded.mobileprovision"' on the command line (see https://developer.apple.com/library/content/qa/qa1798/_index.html for more info). At this point, I knew the provisioning profile was fine, but the archive still gave the same validation errors.
3. Then, in Target -> General -> Signing, I tried manually setting the Provisioning Profiles (turning off 'Automatically manage signing' and set them myself). At this point I discovered that somewhere the Product Bundle Identifier had been set wrong in Xcode, which caused a mismatch with my Provisioning Profile. I finally found the wrong Product Bundle Identifier in Target -> Build Settings -> Product Bundle Identifier.
4. Once I fixed this, it correctly validated. I'm not sure if reinstalling the provisioning profiles helped at all (which explains my earlier 'Well, sort of'), but I'm sure fixing the Product Bundle Identifier helped.
I hope this helps someone else, and I sincerely hope Apple improves their error messages to make this sort of issue easier to debug.