I'd just like to chime in on this because I recently encountered this problem. I bought an iPhone 6S Plus outright and set it up without porting my cell number to the phone, so it was just a wifi only device (wanted to make sure I liked it before going all in). I downloaded the Philips Hue app, paired to my bridge and logged in and all my lights and scenes were there. My Hue tap was still working fine. I bought the Home app and linked it up and setup my Living Room as a room in the app. I connected Siri through the Hue app and was able to control my lights with commands like "Hey Siri, set the Reading Scene" or "Hey Siri, dim the Living Room lights to 30%".
I then returned the phone so I could get one on the upgrade program, but because I had originally received an unlocked version they could not switch it to the upgrade program so I went home with a different 6S Plus on Verizon. I had previously backed up the first 6S Plus to iCloud but could not load this right away because it was made on 9.2 and the iPhone from the Apple store was on an earlier version. I had to set it up as a brand new iphone, do the iOS upgrade, then reset the phone and THEN set it up using my iCloud backup.
I then tried to control my lights through Siri but it found no lights. I went into the Hue app and saw the same message as the OP. I tried logging out of iCloud then logging back in, restarting my iPhone, disabling keychain then re-enabling, resetting Homekit configuration (though I'm not confident this did anything). The Home app also could not discover any of my accessories. I tried wiping the iPhone and setting it up as a brand new iPhone, logging into iCloud and then setting up all my apps again. The Hue app worked fine but again, it said another user already paired the Homekit enabled bridge and said I should ask them to share it with me. But that person was me on a different phone, so that's a problem.
The only way I could resolve the problem was by completely resetting my Philips Hue bridge from scratch. I had to name all my lights again, setup all my scenes again, and set up my Hue tap from scratch. I was finally able to get Siri and the Home app back in control of my Homekit accessories.