I experienced a similar experience with my AT&T branded Sony Ericsson phone running on a Java ME platform. Not sure if AT&T is blocking my access to most streaming audio but it is very rare where I can run streaming audio though the phone does
My phones specs indicate it supports the WMA and MP3 formats but it does not play on both AT&T phones I have.
Not sure if it is a formatting issue, but the scuttlebut on the AT&T forums is the company intentionally blocking many websites that that use a lot of data and I have seen first hand sites that download third party apps are blocked.
Despite an ongoing expansion of their data network, AT&T being the exclusive distributor for the Apple iphone has seen unprecedented demand for Data use resulting in web traffic unseen by other wireless providers. Iphone users account for 85 percent of data usage.
I have found a pretty decent site that recently established a new identity and url at www.Yourmuze.fm . The site pretty much is able to stream to your phone any valid url with streaming audio. The bummer part is most radiorefernce channels appear to change urls about every 24 hours, so I find myself have to cut and paste the new url each time I would like to monitor something on my mobile from here. I think of it as a small price to pay to do what was unthinkable though just a short few years ago.
In addition to feeds from this site there are many other scanner urls both private and otherwise, as well as streaming radio from all around the world in numbers that are endless. Even Howard Stern can be found here without paying the Sirius/XM price 24/7. It's free and will work on the Solstice which is built on the J2ME/Java ME platform.