Okay what's happening is that the Pandora update service gets terminated when you put the app on the background. As soon as you hit the home button and make pandora disappear to the background, it's run as a secondary server process.
By default Android terminates secondary server processes when the phone runs below 20MB free RAM or something (Not sure about this value). The only way to fix this is for the dev to either make Pandora a "visible" application, or change the OOM pririoty values.
or you can just use a task manager and kill dormant apps/processes before running pandora.
OR
You have to download auto memory manager/autokiller and change the secondary server value to something really low like 8MB or 10MB. I can confirm that this works.
I figured it would be something like this. Thats one of the reasons I started using Apps2Sd yet I still have the problem. Shouldnt apps2sd fix it? How has this issue gone for so long without getting much attention? I keep saying that i will never use Pandora again because its so annoying but I end up coming back...