We've now tried this on Monterey. There's still an issue but I think we learned a bit more:
We created a fresh user account on the machine and logged-in to iCloud/Books/App Store/TV with an Apple ID which did not have Apple Music access. We logged-in to Music with an ID which had Apple Music access and enabled "Sync Library" from within the Music app
At this stage, as before (on Big Sur), SKCloudServiceController().requestCapabilities denied that the user had ".addToCloudMusicLibrary" capability (even though they clearly had)
Because the Apple ID we used for Music had not previously been used we opened the Music app and tried a variety of operations to make sure that they could play tracks / playlists / albums Ok and that we had the right authorisations. This was the same Apple ID we had used for our Big Sur testing
As part of this we created a playlist in the user's library and then deleted it. Immediately after we did this, SKCloudServiceController().requestCapabilities started returning ".addToCloudMusicLibrary" capability
So it seems as though creating an initial playlist in the account "kicked" it into life. Given that most of our users are new to Apple Music it's entirely possible that they have not created playlists before running our app, which might explain why we get this error so frequently.
Unfortunately we only had the one spare Apple ID with unused Apple Music capability so we haven't been able to repeat the above steps to confirm. Now the account has started returning .addToCloudMusicLibrary it always seems to work on any machine.
Also FYI we have not been able to reproduce the issue where we managed to create playlists in the wrong account on Monterey, which is definitely progress.