I am having this same issue and did the steps above,
I am still getting "Accessory not found, You made need to retsarted your accessory before you can add it to your home."
I've rebooted my C5, Ive factory reset my apple tv, I have no idea where to go from here