There is a possibility that you are experiencing the infamous "broken Sprint proxy" problem. You might want to try the solution described here: Moment - Guides and Tips
I was unable to stream using some apps until I applied the fix.
Note that you can also get your MSL (a six-digit code that you will need to do this fix) using an app from the market called MSL Reader; to use MSL Reader will require that you be rooted, which you can do temporarily using a non-Market app called VISIONary: http://forum.androidcentral.com/htc...emp-root-your-evo-shift-update-1-30-10-a.html
Yeah my phone was doing the same thing! I found the proxy fix else where on the net and it worked like a charm! Thanks Analog for links I'm sure they will be very helpful for a lot of people.
My shift does this sorta. Mostly its half way through a song and it freaks out and I get 30 sec of no music and then it either skips to the next song or gives me that error message. I went to the links and didn't find any proxy fix.