Grooveshark, the premium streaming music application we looked at previously has rolled out an update recently. Sadly, no changelog was issued with the release but users opening up the application were indeed, prompted to download what is now v1.0.7. Seems a lot of T-Mobile users were having issues with getting the application to work previously, so maybe you'll want to give this version a shot to see if it works better. Grooveshark is available for $3/mnth through their VIP program which allows for unlimited streaming and caching of music played for offline usage.
