My wife and I have both had a number of problems with Pandora on our phones, even when we were using BBs and not Android phones. The main issue I've had with Pandora on a mobile device is that it seems to have trouble getting the stream going again after encountering loss of a signal or a even a weak signal. It will sometimes sit for minutes without doing anything. Sometimes, I have to close the app down and restart it just to get it playing again.
I only recently learned that Pandora actually limits usage to so many hours per month. If they expect mobile users to pay for a subscription to their premium service, they really need to make their mobile app more robust. Honestly, if it were more reliable, I would seriously consider paying for Pandora One, but since I mostly use it on my Droid, it would only frustrate me to pay for something that has so many hiccups.
Now, if I had a Google TV device that could stream Pandora over my home network and through my sound system, that might be enough to change my mind...
-SR-