Did you add a new remote in your AppleTV settings?
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).