Ok, after troubleshooting, if I'm on the main screen with Audio, Video, Playlists, and Remote and tap on search, the box is hidden.
If inclick into one of the categories and click on the search from there, the box shows up.
When you tap on Audio, it defaults to a hidden search box. If you tap RETURN, that hidden search box goes away. Then you can tap on search and the box will show up.