HomeKit "Apple TV not responding"
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:


Change my Apple Id from @me.com to @icloud.com. You can do this by logging in to https://appleid.apple.com/
Delete my home from the home app on all devices (including family).
Log out of iCloud on all my devices.
Log back into iCloud on my iPhone.
Create a new home and add my homekit accessoiries.
Log back into iCloud on my Apple TV.
Invite my family to the home.