Hello Softbrain, and welcome to Seven Forums. I don't have a lot of experience with downloading music Soft, but may I suggest that instead of clicking on the "browse all online stores" you try just clicking Windows Media Guide. From there you have a drop down menu for Music as well as a search engine in the top right corner. If you're just getting started with WMP 12, you may need to find and add stores.
A second choice might be to just select a store at random and see if that store offers the type of music you're looking for. Good Luck