Having the same issue here. ONLY ON 3G.
I too am on AT&T with a grandfathered unlimited plan. I'm only at 700 MB now and am usually on a wifi.
Pandora works flawlessly while on a wifi network, but the minute I stray from the network or turn off wifi, the slowness starts. Minutes to load the next song.
FWIW, I use the Radio.com app a lot. I have NO problems catching a station and holding it. Data throughput "appears" fine in most of my other apps, downloading emails, and pulling up pictures on Facebook. This seems to revolve a LOT around Pandora. I suspect AT&T is looking at whatever network ports the Pandora app uses and is throttling those ports.
I pay for service from AT&T and I pay for PandoraOne. This pisses me off, as I use Pandora DAILY in my car. The day the next gen iPhone drops, I'm outta here, AT&T.