At reddit we solved the problem by writing the most often called parts in C and using c extensions. There is definitely more work to do there, but overall I think Python gets a bad rap as far as speed is concerned.
It's certainly not the quickest, but it isn't a dog either.