Do not give up on threads altogether. As the research quoted in the article shows, threads are still a very valuable technique in many cases.
Using Python from multiple threads, however, can impose significant overhead due to contention for the GIL. For example, if you embed Python, your threads cannot safely access the interpreter without holding the GIL. See Thread State and the Global Interpreter Lock in the Python/C API Reference Manual.
An alternative is to use processes instead of threads in your application. Such an approach is particularly promising for computationally intensive tasks on multi-processor architectures. There was an interesting talk on this topic at PyCon last year. The ideas and results presented by the authors (see previous link) should be helpful to you. You may also be able to use their project (called POSH) directly, although it is still in its early stages.
In any case, it is important to take the time to think about the implications of the various available techniques in your specific situation. It is also highly beneficial -- and usually essential -- to experiment with different approaches before making a major design decision. Above all, do not feel pressured to throw away your work just because it is not entirely conventional, or requires a less popular methodology for successful completion.