I don't know if our issues are the same but just in case, try waking the Apple TV up first by the little hand held remote that came with the Apple TV. I've found that once the Apple TV is awake the remote app on my phone can find it and connect. If it's not awake it just spins and then says it can't locate an Apple TV. Of course that totally defeats the purpose of a remote app. I'm assuming this is an iOS 7 problem since prior to it I had no problems.