I tracked down the whole HTTP response in the logs, and it turns out the error message had been misidentifying which operation had failed. I now know what’s going on, and how to fix it. Not a problem with associations after all! Sorry for the misinformation.
There is a problem with timing when creating contacts and then trying to fetch associated companies, but it’s fixable by making the client pause for a second or two to let HubSpot finish what it was doing. (The whole sequence is running synchronously.) I’d already put that pause in, but I was wondering why it was still failing.