I got a Nokia n900 phone, which has the same CPU as the Pandora and is very similar in many ways. It also runs Linux (maemo 5, based on Debian). They have a kernel in the testing repository which supports overclocking the normally 600Mhz CPU from 125Mhz up 1.150Ghz which is twice the normal speed. I tried this out, and it does work very well: my programs (graphics demos) and gcc compiles do run twice as fast. I ran it at the high speed for over an hour with no visible ill effects or crashes. I think it's safe enough.
But I think the CPU governor (which automatically adjusts the clock frequency based on load) should be more conservative, and keep the clock speed low as much as possible unless the CPU usage gets above 90% I'm sure there's a way to do that.
You can also reduce the voltage, for better battery life, supposedly up to 48 hours. I suppose it will be possible to do all these things on the Pandora, as the processor is the same. I'm looking forward to running N64 games at 1.2Ghz on my Pandora
Quake 3 Arena on the n900 doesn't seem to run much smoother at the high clock speed, which suggests the GPU was a limiting factor for Quake. The n900 and the Pandora both have a slower PowerVR GPU than the iPhone 3GS, but quake does run at over 25fps and feels smooth like a TV. I'm really happy with this phone and I think it will complement my Pandora very well. I encourage other people to buy one, and support Nokia's choice to make maemo Linux a very open platform. They cost about AU$500 now, or according to US ebay, "New from: $479.99, Used from: $450.00". I want to work on cross-porting / compatibility so that Pandora apps / environment will run on the phone and vice-versa. Nokia encourages people to hack this phone (comes with xterm, can get a root shell, can apt-get install software from Debian).
I don't feel I'm spamming by recommending this phone. I am genuinely impressed, and I think it will go very nicely with the Pandora. The Pandora will be better in some ways, especially for gaming, and the phone will be better in some ways, e.g for making phone calls! I'll be happy to have both when the Pandora is finished!