Pandora worked great with Airplay or whatever it is called. I was playing music form my iPhone to my Apple TV for a few hours and then, boom, it is gone. Is its existence a glitch or its absence?
Try rebooting your iPhone 4. I had video working via AirPlay, but no audio apps (iPod nor Pandora) showed the capability to stream via AirPlay. I rebooted, and it all came back.