OK Update w possible fix
So I got my new phone..I had to call to get it activated again. With the rep still on the line, I installed Pandora and tested it out. It STILL DID NOT WORK.
At this point I chalked it up to a Pandora issue with the 32gb version, as it seemed through this thread, only the 32GB version was having issues. However, the rep seemed very willing to stay on the line w me and sort this out.
After about an hour of going through different things, and both of us researching online to find stuff, he put me on hold to talk to the advanced tech team. While on hold, I was still tinkering around with the phone, and under Settings, More Settings under Wireless and Network, and Mobile Networks, I switched the Network Mode from the default CDMA settings to LTE / CDMA. By theory, this really shouldn't have any bearing on the issue, since LTE is not available and it should just default back to CDMA. However, lo and behold, IT WORKED. I rebooted the phone, went into Pandora, and it started playing over 3G. I tested went through several songs, rebooted again, and it still worked.
I still have to see if this sticks, but for right now it seems to have done it. I'd be curious to see if this works for anyone else.