Theres a tweak in cydia that will spoof your location I've never used it and don't know the name. Locaholic maybe? Not sure it's even compatible with 5.1.1. Worth a shot though.
I looked it up. The one I was thinking of is called locationholic and it looks like for the current iOS you also need locationholic fixer. Is that the one you tried? It says it works for find my friends. Maybe it'll work for pandora?
I think the tweak you speak of is just to fake the location of your gps. To be able to use pandora I need to find a way to fake a U.S IP, as Pandora looks at the IP location and not GPS location, but I'll still give it a shot, I'll get back to you and let you know if it worked.
OP did you ever find a solution? I'm about to take a trip and I'd like to be able to use pandora on beach.