My Python FPS increased to about 30 once I started printing out the time only once every 16 frames. The C++ version you posted gives me about 230FPS.

I've got Pentium Dual core 2.10 GHZ with 3Gb RAM and 32bit Windows 7. I'm also running CPython 2.7.2

This touches the reason that i have shied away using libraries such as pygame after my initial experiments. After years of experimenting with game frameworks implemented in Lua and Python, I've come to the conclusion that you should not implement your "inner draw loop" within Python or Lua. You spend way too much time trying to optimize it, just to get it into an acceptable range. Much better to implement your inner draw within C or C++, where even an un-optimized version can typically run much faster than an implementation in script. Construct an interface to the inner draw loop such that you can add/remove instances of sprites, but leave the actual render loop to a faster language.

It's not just for rendering, either. Any time you have an inner loop (a loop that iterates over a data set every frame; physics comes to mind) you probably want to offload it into a C/C++ module and implement an interface exposed to script. The right tools for the right job; libraries like pygame, IMO, tend to be counterproductive in this regard.

I was already planning to do the physics in C++, but I figured it might be easier to do all the UI stuff in Python.

My advice? IMU, there's compilation tools for Python - Try compiling it. Interpreted languages will always be slower, barring crippleware.