Does this happen with every song you are trying to search for? Because I too have had this happen with the ocassional search. What I do is if I tried to search for a song by using the Artist's name I would try their name and the genre of that song. Try it. It might work.