I made some MP3 files and uploaded to my Samsung Nexus. Google Play Music (GPMu) would find the files but when I tried to play any of them, it displayed "Couldn't play the track you requested". If I select the files individually using a file browser, I could play them with GPMu, so the file format was recognised. Clearing GPMu's cache and data did not fix the problem.
My workaround was to attach an image to each file using a media library manager then reload the files. Now GPMu can play the files.