In essence I have the following loop running in thread A:

while True:
    with self.lock:
        time.sleep(0.1)

I then try to acquire the lock in thread B. This blocks forever on Linux, but runs fine on Windows XP.

The following modification makes the code behave as expected on Linux:

while True:
    time.sleep(0.001)
    with self.lock:
        time.sleep(0.1)

See the attached file for the full example. Python versions are:

Python 2.6.4 (r264:75706, Dec  7 2009, 18:45:15)
[GCC 4.4.1] on linux2

and

Python 2.6.4 (r264:75708, Oct 26 2009, 08:23:19) [MSC v.1500 32 bit (Intel)] on win32

You are just having wrong expectations. Releasing a lock doesn't guarantee that any other thread waiting on it will be scheduled preemptively. So, if you re-acquire the lock immediately, the other thread will not necessarily have had the opportunity of running at all. Whether or not threads do get switched at that point is highly system-dependent.

There are many synchronisation primitives you can use (locks, events, queues, condition variables...), each for a different purpose. I suggest you post on comp.lang.python if you want more help on the subject.