Back into the swing of things....
So I've been researching NumPy, a Python module for doing fast things with arrays, to see if it might help speed things up a bit. Looks promising, although to get the speed advantage I'll have to redesign the code somewhat to use parallel arrays instead of a single 2D array of objects.
I discovered, with Psyco, the code is slight more than twice as fast as with it off. On, I tend to get framerates in the 40-50 range, off, around 22-25. But alas, Psyco's homepage now lists the project as officially abandoned, which is kind of a blow honestly. Its successor PyPy isn't universally useable yet -- in particular, it's incompatible with Pygame.
Another possibly useful modules/packages is Cython, which is a more explict method of compiling Python code, but has the disadvantage that the best optimizations requires peppering the code with variable type declarations, which are not legal Python in themselves, so it's not a drop-in system.