Not sure if you have solved the problem, but I came across this thread while trying to find out how to fix my phone. I ended up clearing the cache from Pandora and it started working like normal again (Settings > Applications > Manage Applications > Pandora > Clear cache). Not sure if this will work for anyone else, but it worked for me
Have you tried the higher quality setting? Menu>preferences>cell network audio quality. There is a normal and high setting. I use the normal and it doesn't bother me, but maybe u should try the high setting.