Hey there and best wishes from spring-time Colorado!
I have had this same problem recently, and noticed my friend was experiencing the same issues.
I decided to reinstall Remote.app (the Remote application). I understand that this may not be the answer you wanted to hear, but it did provide an immediate resolution and restored this feature.
For an overly obsessive-compulsive way of doing this, follow these steps:
1) Delete 'Remote.app' from iOS device
2) Restart iOS device (shut down, power on)
3) Download 'Remote.app' from App Store (either search for 'Remote' or find it in your purchases, or load from iTunes... Easiest is to just search for the app on App Store)
4) Launch Remote.app and turn on Home Sharing, using iTunes username and password
5) Select Apple TV, navigate to Netflix search; functionality should have returned!
Best wishes and good luck!