Is it just me or is there no search option in the music player??
I am unable to search for songs!! HELP!

I have the exact same problem. I even downloaded a file manager to create a folder in the music directory but still nothing came up in the music player I even tried 3 more different music player from market still nothing happened.

Unfortunately the build in Player has not that option, but there are plenty others in the Play Store

-----
Grüße von Andreas - Die Regeln > Unser AppCenter > Das Buch für Einsteiger - kostenlos > Apps nach Einsatzzweck

You guys should use the Google Music app if you can found here:

https://play.google.com/store/apps/details?id=com.google.android.music&hl=en

It has that option. If you dont live in the US, there are still ways of using the player, but you wont be able to buy music.

This worked for me:
Phone Settings => Apps => Music App => Clear Data