Behind the scenes you see (via MITM) that it tries to connect, but the device rejects the request because it doesn't have the local auth token (which can only be retrieved using a linked account).
This is a good design: the device owner (or any other previously linked users) are allowed to reconfigure the device while it's in setup mode if this is ever needed, but unauthenticated users cannot. And if the device owner loses access to their account somehow, they can use the factory reset button on the bottom of the device to set it up with a new account. (Unfortunately, it was broken, as I described.)
So I think the main "bug" here was the exposure of the "cloud_device_id" and other sensitive device information required to link an account in setup mode, even though it's not used by the Home app to reconnect a device to Wi-Fi. My suggested fix was simply to stop returning this info in setup mode. Last I checked this behavior hasn't changed though so I guess it was easier to make changes on the server side to fix the issue.
Btw, they later updated the Home app's UI to provide a more descriptive error message than just "could not communicate": https://i.imgur.com/ISWk4Bj.png