The App Store cache was not updating according to the new setup. In our case it took almost 2 months to get fixed by itself, and while in some countries the issue was fixed, in some others it wouldn't. It's a terrible issue with the App Store cache, as people who paid for your app cannot download the new companion. Still, it's Apple's fault for not refreshing the cache when a change like this is introduced and only when the global App Store cache gets refreshed (which could take days or months in the worst-case scenario). BTW: To your question @objectivist, uninstalling and installing again won't solve the issue while the App Store cache remains outdated. You can uninstall and install but only the Watch app, never the iPhone/iPad app.

Same issue here. We used to have an Apple Watch only app, and now we released the companion app and our existing users can't download the iPhone app :( Has anyone found a solution for this?