Pandora's initial problem was the same as what Rovio had with Microsoft. i.e. Microsoft jumped the gun by name-dropping Pandora before they had officially committed to developing for Windows Phone.
They now also believe that Windows Phone needs to gain a significant share of the market in order for them to justify supporting the platform. c.f. Pandora does support the Blackberry platform. (However, it is notable that Pandora supports both WebOS & Windows Mobile even today.)
Finally, there is a technical issue involved as well. Initially, Pandora stated they needed access to a background audio API before they'd publish a WP app. Then, once it was added, they realized that the WP Marketplace certification requirements state that the background-player controls may not display ads, which Pandora does not agree with as they believe this would either cut into their free-tier revenues or prevent them from offering the free-tier on WP.