I'm not sure how well this will help for the particular application you're working with, but here are two approaches borrowed from functional programming for writing multithreaded code:
Immutable objects
If you need to share state between threads, the state should be immutable. If one thread needs to make a change to the object, it creates a brand new version of the object with the change instead of mutating the object's state.
Immutability does not inherently limit the kind of code you can write, nor is it inefficient. There are lots of implementations of immutable stacks, a variety of immutable trees that form the basis of maps and sets, and other kinds of immutable data structures, and many (if not all) immutable data structures are just as efficient as their mutable counterparts.
Since objects are immutable, its not possible for one thread to mutate shared state under your nose. This means you don't need to acquire locks to write multithreaded code. This approach eliminates a whole class of errors related to deadlocking, livelocking, and raceconditions.
Erlang-style message passing
You don't need to learn the language, but have a look at Erlang to see how it approaches concurrency. Erlang apps can scale pretty much indefinitely because each process is completely seperate from all the others (note: these are not exactly processes, but not exactly threads either).
Processes fire up and simply spin a loop waiting for messages: messages are recieved in the form of tuples, which the process can then pattern match against to see if the message is meaningful. Processes can send other messages, but they are indifferent to whoever recieves the message.
Advantanges to this style is an elimination of locks, when one process fails it doesn't bring down your entire app. Here's a nice summary of Erlang-style concurrency:
answered 2009-01-29T21:01:14.327