I have the exact same issue and it is so frustrating. I upgraded to YouTube Premium for the kids as well so they could play music on their Nest Mini's without stopping me from listening to other music on my phone whilst walking the dog, but if they can't connect to the devices, that won't work.
Same problem here. The so-called fix of deleting updates and then reinstalling the updates does nothing either. This is clearly a fault that Google simply can't be bothered to fix. Shame on them.
We haven't heard from you in a while so we'll be locking this thread if there is no update within 24 hours. If you need assistance or want to discuss topics, feel free to start a new thread.