I find that 99% of the time that you need to use threads for CPU work (not just IO), that means that you care enough about performance that your Python just calls into some C library (C extension libraries e.g. numpy, scipy, or even bits of the standard library e.g. zipfile operating on an in-memory buffer). The thing is, all these calls (almost) all release the GIL anyway. So threading support in Python is already meaningful, unless you want to run pure-Python CPU intensive code on multiple threads, which I'll admit does happen but in my experience is rare.
Unfortunately we're mostly dealing with complex stuff happening during graph traversals. There is no "inner loop" for us -- just the "outer loop" of the graph traversal. So the only way to get our code to run in parallel is to port the whole algorithm to C. But that's 150k+ lines of codes, there will be barely any Python remaining :(
IMHO Python is a trap, it's easy to get started with but you can stuck in a position you can't get out of without a full port to a different language. (and yes, we've already tried multi-processing and using shared-memory segments in the C code portions to avoid re-doing work in every process, ... but after more than a man-year of work, >80% of our application remains single-threaded thanks to the GIL, even though in any other language it would be trivial to parallelize the independent graph traversals)
It's neat to have a scripting language for fast prototyping but we would be much much better off if we had picked Javascript instead of Python (the ability to have multiple interpreters in the same process running in parallel would solve our issues).
As I said, my experience is that this is not normally a problem in practice. Clearly that's not your experience! I'm not sure whether I've been unusually lucky or you've been unusually unlucky.