Try changing up your search terms a little. Search for just the name of the artist or the name of the album. Try using the all types search instead of just audio or video. Try searching at different times of the day, as different users log on your search results should change.
This thread has more tips
How to find music. Same principles apply to music and movies.