small FYI, you have to put everything on beta to get hub choosing (phone, aTVs, and homepods). The phone, aTV and HP public betas have been stable for me. But as always, they are beta, and just because they work now, doesn't mean they'll work on the next update. A few years ago, the aTV beta lost ATMOS for one version after it had been working fine for several previous beta versions, it was back the next update.
and I hate to say this, since people get grumpy when it's suggested, but...
sounds like a network problem, have you tired rebooting your router?
hubs advertise themselves using mDNS (bonjour). its just a network packet that goes to a special broadcast address, so your network gear forwards to everyone, and all/most of your devices will hear it. Sometimes network gear can get bogged down with broadcast packets, rebooting usually clears that out.
you don't have any odd network segmentation do you? everything is on one big LAN? Sometimes routers can block connections between the wired and wireless segments of your network. and possibly also block between different SSIDs
discovery mdns browser available on both iOS and Mac app stores (free) It lets you see all of the mDNS packets on your network. I'm not home and don't remover exactly, but you should see entires for homekit and hap, one is homekit hubs, the other is devices like bulbs. You should also see airplay listed. if you click on the heading, you should see a litst of all devices that support that service. You should also see entries for your printers, and computers with network shares. If you have different SSIDs or a 2.4 and 5gHz network, I'd move your phone/laptop to the different networks and see what happens.