I had a 4th Gen Apple TV setup as my HomeKit hub and was working fine. Lately I've noticed the Home App on iPod/iPhone says "Apple TV not responding". I've done all the tier-one support obvious things: Updated iOS and tvOS, cycled power on and off, signed out/in on Apple TV cloud login, etc.
About at wits end, the Apple TV hub seems to be necessary for any newly added devices to show up on other home users (that I invited) iPhones. There will be unrest among the natives soon if I can't make this work.
Best Answer
Quick summary: log in to https://appleid.apple.com/ and change your Apple Id from @me.com to @icloud.com
I recently had the same issue (including homekit invites getting stuck as described in this issue HomeKit invitation stuck). Yesterday I was finally able to resolve this problem after having tried all the obvious things as well (resetting devices, logging out/in of iCloud etc).
Turns out the root cause was some kind of conflict between my Apple Id and iMessage. After taking the following steps everything started working properly again: