Remote app won't connect, says "Turn on home sharing" After an update installed, none of my iOS devices recognize my Apple TV from the Remote App. They just say "Turn on Home Sharing..."

When I go through the "add remote" wizard, I see a disabled music icon. I can't do anything with it except delete it.

What am I missing?
I play a song on my phone and then close AirPlay and select Apple TV which wakes the device. This works most of the time.