I was one of the many that went through the Pandora heart ache. It really did not matter what I did with either: Debian Sid or Mint 12 that I currently have installed on my linux box.
However, have you had a chance to look at last.fm?
It does everything Pandora does, albeit the playlists aren't nearly as convenient as the stations on Pandora, but it is free for the for seeable future unlike Pandora's new-ish business model. It is available in the repo's with pretty much 0 configs out the gate aside from an easy to setup account.
I was reluctant to leave Pandora after years of setting up my lists and tweaking things the way I wanted, but I was not willing to pay a fee for something that is pretty much free to being with.