I've had these problems for some time.
First...even when fully connected to Wifi, my Samsung Galaxy S3 (ATT) won't play a song, despite me pressing the song title over and over again. Eventually (a minute or so) the song begins to play,
Secondly...even when fully connected to Wifi, it takes forever for an album to load, or for the "back" page to load. I just get the progress circle for 20-40 secons.
Thirdly...and this has started recently...songs will randomly pause during play. It has nothing to do with a change in cell / wifi, as this happens even when the device is stationary.
I have uninstalled and reinstalled over and over again. Nothing seems to help.