Pithos and Pianobar, for the win.
DoR answered my question on how to set up pianobar to scrobble to last.fm. Not quite user-friendly, but hey, it’s a command line pandora client, you’re not going to give up when you run into CPAN are you?
Matthew however, pointed out Pithos, a GTK client for Pandora with built in last.fm scrobbling. I head-desked myself for not knowing about this app sooner.
There’s a bug report for MPRIS/SoundMenu support, I’ve mailed the author to see if there’s a way we can help. In the meantime, rock out to the AC/DC.