The strange thing is this is only happening for me on Android.  If I use Google Music through Firefox on my PC and, for example, try to play a song by Midnight Oil, I get a song by Midnight Oil.  If I try to play the same song in the Google Music Android app, I get a random techno song from elsewhere in my library.