Did you add a new remote in your AppleTV settings?
hmmm... This didn't help unfortunately. I've even totally restored my ATV back to factory.
And you turned on Home Sharing? On the Apple TV, Under Settings > Computers. Need to do it on each Apple TV.
Have just confirmed that the remote app only seems to work when the ATV is connected via WiFi. As soon as it switches to ethernet connection, Remote App can no longer detect the ATV.
Weird. Can you still airplay to that ATV from your iPhone when it's connected via Ethernet? Or is it totally invisible from the phone (not just Remote app)?
If it's not visible at all to the iPhone, check your router config - it's possible that you have your wifi and your Ethernet networks on separate subnets (which Bonjour won't handle).