Hi, I just stumbled upon this post while researching the issue myself. We were getting similar reports and I was just as confused as you @chrisonline as we only register the tiles without any added complexity. I spent a good amount of hours today and I seem to have been able to fix it by using a Receiver that listens for the BOOT_COMPLETED and USER_UNLOCKED events which will then update the tiles, making them available again. I suspect this is related to changes in Android 16s boot sequence as we didn't have this issue before.
I will add the PR in our repository and the relevant issue comment below. Feel free to remove this comment and/or mask the links if it's considered spam or self-promotion which understandably are probably against your rules. I just felt like sharing this with you so you don't waste hours of your time trying to fix this issue.
Pull request: #1761
Comment with added context: #1710-3765395662