The search function is not working from the FireTV app. No results are found for anything I search. This have tried from multiple FireTVs. Works fine on standard Android. Any thoughts?
Sadly, it seems you and I are the only people using FireTV as yours has been the only response in 6 months. 
Have you tried the alpha build? This should be fixed there with the new navigation
Heh. Plenty of us use Fire TV, but I guess few use Search.
As I understand it you'll use the client to install the beta, then go back to the same place on the menu to install the alpha:
https://community.getchannels.com/t/alpha-channels-3-0-for-android-tv/22979